題意：從一個非遞減序列中找出k個3元組(x,y,z),其中x<=y<=z,一個三元組的代價是(x-y)^2，要求這k個三元組的代價和最小。
解法：DP，令a[i][j]表示從前i個數(shù)中選擇j個3元組,那么轉(zhuǎn)移方程為：a[i][j] = min(a[i-1][j],a[i-2][j-1]+w(l[i],l[i-1]))；很好理解，如果使用l[i]，那么肯定要和l[i-1]一起使用(因為序列是非遞減的，可以證明),所以就有了第二個轉(zhuǎn)移方程，如果不適用l[i]那么它就和i-1個數(shù)種選擇j個三元組的結(jié)果一樣，注意當(dāng)3*j>i時無效。
還有一點(diǎn)需要注意的就是如何選取z確保z>=x>=y，看了人家的提示才知道，把數(shù)組從到小排列，這樣就不需要考慮z的影響了。從發(fā)覺自己還沒有領(lǐng)悟DP，狀態(tài)設(shè)計還需要看人家的思路才能寫出來，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;
}