1246: 羊羊列队

内存限制:512 MB 时间限制:4.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:121 通过:23

题目描述

在修建完新路后,小羊们总算可以安心入学了。今年是羊年,新入学的小羊特别多。老师们打算将N只小羊分成M个班级,每个班至少有1只羊。

如何分班成了老师们最头疼的事情,因为开学典礼上,村长就要看到小羊们列队的情况。每个班的小羊都排成一排,站在草场上。村长希望队列中羊的高度尽可能整齐,村长对队列的不整齐度有自己的要求。

例如队列中共有t只羊,高度依次为A1A2……,At。那么不整齐度为:(|A1-A2|+|A2-A3|+……+|At-1-At|)2。即相邻两只羊高度差之和的平方。

而总体的不整齐度,就是各班不整齐度之和。

现在,请你帮助老师们设计一下,如何分班,如何列队,才能使M个班级的不整齐度之和最小。

输入格式

第一行两个整数NM,分别表示共有N只小羊,要被分成M个班级。

第二行N个整数,表示每只小羊的高度Ai

输出格式

输出最小的不整齐度之和,结果保证不会超过231-1

输入样例 复制

4 2
4 1 3 2

输出样例 复制

2

数据范围与提示

【样例解释】

分成两班,4和3一个班,1和2一个班,不管怎么排,两个班的不整齐度都是1,不整齐度之和为2

【数据范围】

30%的数据,1<=N<=10;1<=M<=5;

70%的数据,1<=N<=300;1<=Ai<=1000;

 100%的数据  N<=10000,M<=1000