題目鏈接： uva-10271 - Chopsticks 題意 劉汝佳請了K個客人到他家吃晚飯，加上他的家人：他的老婆、兒子、女兒、媽媽、爸爸、岳父、岳母， 那麼這頓晚飯一共有K+8個人。因為是吃中餐，所以需要筷子，他家裡一共有N根筷子，而且長短不一， 這時劉汝佳的ACMer本性又暴露出來了，他不按照正常的每個人都給兩只筷子，而是每個人分3根筷子， 其中最長的一根用來叉比較大塊的食物，而另外兩根較短的筷子當作正常的使用。為了讓每個人用得 更加舒服，顯然，要讓短的兩根筷子長度盡量接近,設這三根筷子的長度為A,B,C(A<=B<=C)，那麼較小 兩根會有一個平方差（A-B）^ 2。劉老師要你幫他算，怎樣分配，所有人的平方差之和最小？ 思路 long long ago，這題已經放著很多天了吧，可能有兩個星期了。 期間本來想和nothi討論一下，結果他說在高中時做過，好吧，搞過noip的人題目就是做得多。。。 然後去翻了下那道noi題(njupt 1581)，看了下發現原題很簡單。 原題是每個人只要兩根筷子，要讓所有人的筷子長度平方差之和最小。那麼顯然從小到大排序一下， f(i, j)表示前i跟筷子，分配給j個人的最小平方差之和。因為所以加道理，可以知道一定要選擇相鄰的兩個 筷子才能讓平方差盡量少，所以得到狀態轉移 f(i, j) = min{ f(i-1, j), f(i-2, j-1) + (len[i]-len[i-1])^2 } 可能正是因為先AC了原題，所以一直限制了我的思路，一直按照上面類似的思路，從小到大排序，然後狀態轉移， 但是因為多了第三根最長的，所以不好想。 如果從小到大排序的話，狀態表示會有一個問題， f(i, j)的第i根，一定是最大的那個，所以他一定不會取，這樣 就給狀態轉移帶來了困難。 後來的某一天，終於想到了：要是從大到小排序會怎樣呢？那麼f(i, j)的第i根，一定是最小的那根，所以他就可以 取了！ 然後還有一個問題，要確定以i, i-1作為一雙筷子時，前面還有一根筷子可以作為三根最長的那一根，那麼， 只要保證(i-2)-(j-1)*3 >= 1，即前面j-1個人分配完以後至少還剩下有1根筷子，就一定可以作為當前i, i-1組 的最長那根！ 狀態轉移就這樣出來了： 當(i-2)-(j-1)*3 < 1時 f(i, j) = f(i-1, j); 當(i-2)-(j-1)*3 >= 1時 f(i, j) = min{f(i-1, j), f(i-2, j-2) + (len[i]-len[i-1])^2} Perfect！ 代碼
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : uva-10271 Chopsticks * @description : dp * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : [email protected] * Copyright (C) 2013/09/02 23:45 All rights reserved. *======================================================*/ #include <iostream> #include <cstdio> #include <cstring> #define SQ(x) ((x)*(x)) using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 5100; int n, m; int len[MAXN]; // 前i個筷子，j個人使用 int f[MAXN][1010]; int main(){ int nCase; scanf("%d", &nCase); while (nCase--) { scanf("%d%d", &m, &n); for (int i = 1; i <= n; ++i) scanf("%d", &len[i]); m += 8; memset(f, INF, sizeof(f)); for (int i = 0; i <= n; ++i) f[i][0] = 0; for (int i = n-2; i >= 1; --i) { for (int j = m; j >= 1; --j) { f[i][j] = f[i+1][j]; if (f[i+2][j-1] != INF && (n-i-1)-(j-1)*3 >= 1) f[i][j] = min(f[i][j], f[i+2][j-1] + SQ(len[i]-len[i+1])); } } printf("%d\n", f[1][m]); } return 0; }
