问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1015思路:
最小差最大和问题
这题...一点想法都没有，就是不会写，只好上网搜索人家的思路，总结如下
动态规划状态方程:
f(j, k) = f(j-1, x), x+(di-pi) = k
这里，f(j, k)表示选择了j个人，其最小差为k且满足最大和的解
另外，还需要记录已选择了哪些人，因为在状态迁移的过程中，只能选择之前未被选择过的人
1 int base = m*MAX_GRADE; /* 防止出现负数 */
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 }