這題和post office還有uva上的chopsticks都很像，很經(jīng)典的轉(zhuǎn)移方程，類似的思想。
要融會貫通。。。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MIN(a, b) (a < b ? a : b)
int f[2005][1005];
int a[2005];
int main()
{
int n, k;
while(~scanf("%d %d", &n, &k))
{
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
std::sort(a + 1, a + n + 1);
for(int i = 1; i < n; i++)
a[i] = (a[i] - a[i + 1]) * (a[i] - a[i + 1]);
memset(f, 127, sizeof(f));
for(int i = 0; i <= n; i++) f[i][0] = 0;
for(int i = 2; i <= n; i++)
{
for(int j = 1; 2 * j <= i; j++)
{
f[i][j] = MIN(f[i - 1][j], f[i - 2][j - 1] + a[i - 1]);
}
}
printf("%d\n", f[n][k]);
}
return 0;
}