题意：从一个非递减序列中找出k个3元组(x,y,z),其中x<=y<=z,一个三元组的代价是(x-y)^2，要求这k个三元组的代价和最小。
解法：DP，令a[i][j]表示从前i个数中选择j个3元组,那么转移方程为：a[i][j] = min(a[i-1][j],a[i-2][j-1]+w(l[i],l[i-1]))；很好理解，如果使用l[i]，那么肯定要和l[i-1]一起使用(因为序列是非递减的，可以证明),所以就有了第二个转移方程，如果不适用l[i]那么它就和i-1个数种选择j个三元组的结果一样，注意当3*j>i时无效。
还有一点需要注意的就是如何选取z确保z>=x>=y，看了人家的提示才知道，把数组从到小排列，这样就不需要考虑z的影响了。从发觉自己还没有领悟DP，状态设计还需要看人家的思路才能写出来，o(╯□╰)o
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 5005
#define MIN(a, b) (a < b ? a : b)
int l[N], w[N], a[N][1010];
int cmp(int a, int b)
{
return a > b;
}
int main()
{
int t, k, n;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &k, &n);
k += 8;
for(int i = 1; i <= n; i++)
scanf("%d", &l[i]);
std::sort(l + 1, l + n + 1, cmp);
// for(int i = 1; i <= n; i++) printf("%4d", l[i]);
// printf("\n");
for(int i = 2; i <= n; i++)
w[i] = (l[i] - l[i - 1]) * (l[i] - l[i - 1]);
memset(a, 127, sizeof(a));
for(int i = 0; i <= n; i++) a[i][0] = 0;
for(int i = 3; i <= n; i++)
{
for(int j = 1; j <= k && 3 * j <= i; j++)
{
a[i][j] = MIN(a[i - 1][j], a[i - 2][j - 1] + w[i]);
}
}
printf("%d\n", a[n][k]);
}
return 0;
}