以前年少无知，看到这题觉得无从入手，今天，终于看出来，这是一道背包题。
每个人，只有选和不选，如果选了，就会影响某个资源的值，而且人与人之间的顺序不影响答案，这种类型的题目，果断就是背包了。
#include#include #include #include #include using namespace std;int like[202];int dislike[202];int N, M;int f[200 + 1][20 + 1][1600 + 2];char pre[200 + 1][20 + 1][1600 + 2];vector ansList;int testN;const int nil = -2000000;int dp(int n, int m, int d) { // printf("==== %d %d %d\n", n, m, d); return f[n][m][d + 800];}void input() { int i, j, k; scanf("%d %d", &N, &M); if (N == 0) exit(0); for (i = 1; i <= N; ++i) { scanf("%d %d", &(like[i]), &(dislike[i])); } for (i = 0; i < 201; ++i) for (j = 0; j < 20 + 1; ++j) for (k = 0; k < 1600 + 2; ++k) { f[i][j][k] = nil; pre[i][j][k] = 'w'; }}void traceBack(int n, int m, int d) { while (1) { char & son = pre[n][m][d + 800]; // printf("*** %d %d %d %c\n", n, m, d, son); assert(n >= 1); if (son == '+') { ansList.push_back(n); d = d - (like[n] - dislike[n]); n = n - 1; m = m - 1; continue; } if (son == '-'){ n = n - 1; continue; } if (son == 'e') break; if (son == 'E') { ansList.push_back(1); break; } assert(0); }}void run() { input(); int n, m, d; for (n = 1; n <= N; ++n) { for (m = 0; m <= n && m <= M; ++m) { for (d = -800; d <= 800; ++d) { int & ans = f[n][m][d + 800]; char & son = pre[n][m][d + 800]; if (n == 1) { if (m == 0) { if (d == 0) { son = 'e'; ans = 0; continue; } else { son = 'x'; ans = -1; continue; } } else if (m == 1) { if (d == like[1] - dislike[1]) { son = 'E'; ans = like[1] + dislike[1]; continue; } else { son = 'y'; ans = -1; continue; } } assert(0); } ans = -1; son = 'p'; int c = like[n] - dislike[n]; if (n - 1 >= m && dp(n - 1, m, d) != -1) { ans = dp(n - 1, m, d); son = '-'; } if (n >= m && m >= 1 && dp(n - 1, m - 1, d - c) != -1 && (ans == -1 || ans < dp(n - 1, m - 1, d - c) + like[n] + dislike[n]) ) { ans = dp(n - 1, m - 1, d - c) + like[n] + dislike[n]; son = '+'; } } } } int i, ans; for (i = 0; i <= 800; ++i) { if (dp(N, M, i) != -1 && dp(N, M, -i) == -1) { ans = i; break; } if (dp(N, M, i) == -1 && dp(N, M, -i) != -1) { ans = -i; break; } if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) >= dp(N, M, -i)) { ans = i; break; } if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) < dp(N, M, -i)) { ans = -i; break; } } ansList.clear(); traceBack(N, M, ans); printf("Jury #%d\n", testN); printf("Best jury has value %d for prosecution and value %d for defence:\n", (ans + dp(N, M, ans))/2, -(ans - dp(N, M, ans))/2); sort(ansList.begin(), ansList.end()); for (i = 0; i < ansList.size(); ++i) { printf(" %d", ansList[i]); } printf("\n\n");}int main() { for (testN = 1; true; ++testN) run(); return 0;}