poj 1015 Jury Compromise

題目大意：每個人有兩種值Di和Pi，從n個人中選m個人組成集合J，D(J)和P(J)為這m個人的Di與Pi和，使|D(J) - P(J)|最小。若有多個集合J最小，則使D(J) + P(J) 最大。

1<=n<=200, 1<=m<=20 ，Di和Pi最大為20.

註意到Di和Pi的和很小，我們可以用類似背包的思想將所有可能生成的值記錄下來。

路徑用數組記錄，每次加入節點時加入本節點與之前的路徑。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #define MAXM (20 + 5)
 5 #define MAXN (200 + 5)
 6 #define MAXDP (20 * 20 + 5)
 7 int dp[MAXM][MAXDP], path[MAXM][MAXDP][MAXM];
 8 int i, cas;
 9 int d[MAXN], p[MAXN], plu[MAXN], subs[MAXN];
10 int main() {
11     int n, m;
12     while(scanf("%d%d", &n, &m) && n && m){
13         printf("Jury #%d\n", ++cas);
14         for(i = 0; i < n; i++){
15             scanf("%d%d", &d[i], &p[i]);
16             plu[i] = d[i] + p[i];
17             subs[i] = d[i] - p[i];
18         }
19         int fix = 20 * m;
20         memset(dp, -1, sizeof(dp)); 
21         memset(path, 0, sizeof(path));
22         dp[0][fix] = 0;
23         for(int k = 0; k < n; k++)
24             for(i = m - 1; i >= 0; i--) // attention
25                 for(int j = 0; j <= fix * 2; j++)
26                     if(dp[i][j] >= 0){ 
27                         if(dp[i + 1][j + subs[k]] < dp[i][j] + plu[k]){
28                             dp[i + 1][j + subs[k]] = dp[i][j] + plu[k]; // 記錄相同差值的最大和
29                             for(int t = 0; t < i; t++) 
30                                 path[i + 1][j + subs[k]][t] = path[i][j][t]; // 枚舉之前的路徑
31                             path[i + 1][j + subs[k]][t]=k; // 當前節點
32                         }
33                     }
34 
35         for(i = 0; dp[m][fix + i] == -1 && dp[m][fix - i] == -1; i++); // 枚舉最小差的絕對值
36         int temp = dp[m][fix + i] > dp[m][fix - i] ? i : -i; 
37         int sumd = (dp[m][fix + temp] + temp) / 2;
38         int sump = (dp[m][fix + temp] - temp) / 2;
39         printf("Best jury has value %d for prosecution and value %d for defence:\n", sumd, sump);
40         for(i = 0; i < m; i++) 
41             printf(" %d",path[m][fix + temp][i] + 1);
42         printf("\n");
43     }
44 }