【题意】：搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.

【题解】：首先，要想重量差的平方尽量少，那么肯定是选择排序后相邻的物品，所以，第一步是排序。
               设状态dp[i][j]表示已经在前i个物品里面选择了j对物品的最少疲劳度。
               转移方程：
                    dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + calc(i, i - 1)), 其中calc(i, i - 1) 表示第 i 个物品与第 i - 1 个物品的重量差的平方。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 using namespace std;
 6 #define maxn 2050
 7 const int inf = 1 << 30;
 8 int n, k;
 9 int val[maxn];
10 int dp[maxn][maxn];
11 int calc(int a, int b) {
12     int tmp = val[a] - val[b];
13     return tmp * tmp;
14 }
15 
16 void solve() {
17     sort(val + 1, val + n + 1);
18     for(int i = 0; i < maxn; i++)
19         for(int j = 0; j < maxn / 2; j++)
20             dp[i][j] = inf;
21     for(int j = 0; j < maxn; j++) 
22         dp[0][j] = dp[j][0] = 0;
23     for(int i = 2; i <= n; i++) {
24         for(int j = 1; j <= k && j <= i / 2; j++) {
25             dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + calc(i, i - 1));
26         }
27     }   
28     printf("%d\n", dp[n][k]);
29 }
30 
31 int main() {
32     while(~scanf("%d%d", &n, &k)) {
33         for(int i = 1; i <= n; i++) {
34             scanf("%d", &val[i]);
35         }
36         solve();
37     }
38     return 0;
39 }
40