【題意】：搬寢室是很累的,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