問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1015思路:
最小差最大和問題
這題...一點想法都沒有，就是不會寫，只好上網(wǎng)搜索人家的思路，總結(jié)如下
動態(tài)規(guī)劃狀態(tài)方程:
f(j, k) = f(j-1, x), x+(di-pi) = k
這里，f(j, k)表示選擇了j個人，其最小差為k且滿足最大和的解
另外，還需要記錄已選擇了哪些人，因為在狀態(tài)遷移的過程中，只能選擇之前未被選擇過的人
1 int base = m*MAX_GRADE; /* 防止出現(xiàn)負數(shù) */
2 memset(f, -1, sizeof(f));
3 memset(sum, -1, sizeof(sum));
4 /* initialize */
5 for(i=1; i<=n; i++)
6 if(sum[1][minus[i]+base] < plus[i]) {
7 f[1][minus[i]+base] = i;
8 sum[1][minus[i]+base] = plus[i];
9 }
10 for(j=2; j<=m; j++) {
11 for(k=0; k<=2*m*MAX_GRADE; k++) {
12 if(f[j-1][k] != -1) {
13 for(i=1; i<=n; i++) {
14 /* see if i has been used */
15 q = k;
16 for(p=j-1; p>=1; p--) {
17 if(f[p][q] == i)
18 break;
19 q -= minus[f[p][q]];
20 }
21 if(p<1) {
22 if(sum[j][k+minus[i]] < sum[j-1][k]+plus[i]) {
23 f[j][k+minus[i]] = i;
24 sum[j][k+minus[i]] = sum[j-1][k]+plus[i];
25 }
26 }
27 }
28 }
29 }
30 }