题意： 有n个陪审团的候选人，每个人都分别有一个控方和辩方对候选人的打分。要求从其中选出m个人作为正式的陪审团，使得辩方总分和控方总分的差的绝对值最小。
题解： 如果足够熟练的话，看到这样的题目，n个人里选择m个人，其实就是说每个人都只有两个结果：选择或不选择——01背包。确定好之后就可以定义状状态dp[i][j][k]表示i个人里选择j个人辩方总分和控方总分绝对值差为k的最大值。 状态转移方程为：
dp[i][j][k] = dp[i - 1][j][k]; dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][pre] + d[i] + p[i]); #include<iostream> #include<algorithm> #include<cstring> using namespace std; inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } const int N = 210; const int M = 810; const int L = 400; int T, n, m; int dp[N][21][M]; int d[N], p[N], ans[N]; void run(){ memset(dp, -M, sizeof dp); dp[0][0][L] = 0; for(int i = 1; i <= n; i++) d[i] = read(), p[i] = read(); for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) for(int k = 0; k < M; k++){ //不选i dp[i][j][k] = dp[i - 1][j][k]; //选i int pre = k - (d[i] - p[i]); if(pre < 0 || j < 1) continue; // dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][pre] + d[i] + p[i]); } int k = 0; while(dp[n][m][L + k] < 0 && dp[n][m][L - k] < 0) k++; if(dp[n][m][L + k] >= dp[n][m][L - k]) k = L + k; else k = L - k; int cnt = 0, sumd = 0, sump = 0; while(m){ if(dp[n][m][k] == dp[n - 1][m][k]) n--;//没选i else{ ans[cnt++] = n; sumd += d[n], sump += p[n]; k -= (d[n] - p[n]); n--, m--; } } sort(ans, ans + cnt); printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++T, sumd, sump); for (int i = 0 ; i < cnt; i++) printf(" %d", ans[i]); printf("\n\n"); } int main(){ while(~scanf("%d%d", &n, &m) && n && m) run(); return 0; }