题意：n(1<=n<=200)个人，控诉方给每人一个值pi，辩护方给每人一个值di，(0 <= pi, di <= 20)，现要选出m(1<=m<=20)个人，使得选出的m个人的p值与d值的差的和的绝对值最小，如果存在多种情况，选择p值和d值的和最大的。
题目链接：http://poj.org/problem?id=1015
——>>设f[i][j]表示选出i个人时辩控差的和为j时的最大辩控和。
状态转移方程：f[i+1][j+p[k]-d[k]] = max(f[i+1][j+p[k]-d[k]], f[i][j] + p[k] + d[k]), k = 0, 1, 2, ..., n。。
用自己去更新别人。。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 200 + 10;
const int maxm = 20 + 10;int kase, n, m, p[maxn], d[maxn], dx;
int f[maxm][2*19*maxm]; //单个状态需保留正负性
int id[maxm][2*19*maxm];void read() {for(int i = 1; i <= n; i++) scanf("%d%d", p+i, d+i);
}bool isok(int i, int j, int k) {while(i) {if(id[i][j] == k) return false;j -= p[id[i][j]]-d[id[i][j]]; //这行要先于下一行!!!i--;}return true;
}void dp() { //自己去更新别人dx = 20 * m;memset(f, -1, sizeof(f));memset(id, -1, sizeof(id));f[0][dx] = 0; //选0个人使得辩控差绝对值为0（偏移后为dx）的方案有一种，就是什么都不选，此时和为0for(int i = 0; i < m; i++) { //共选i个人for(int j = 0; j <= 2*dx; j++) { //辩控差的和（带偏移）if(f[i][j] != -1) { //自己去更新别人自己必须是可行的for(int k = 1; k <= n; k++) { //枚举新加人员kif(isok(i, j, k) && f[i][j] + p[k] + d[k] > f[i+1][j+p[k]-d[k]]) {f[i+1][j+p[k]-d[k]] = f[i][j] + p[k] + d[k];id[i+1][j+p[k]-d[k]] = k;}}}}}
}void output() {printf("Jury #%d\n", ++kase);int Min;for(int i = 0; i <= dx; i++) {if(f[m][dx+i] != -1 || f[m][dx-i] != -1) {Min = f[m][dx+i] > f[m][dx-i] ? dx+i : dx-i;break;}}printf("Best jury has value %d for prosecution and value %d for defence:\n", (Min - dx + f[m][Min]) / 2, (f[m][Min] - Min + dx) / 2);int ret[maxm];for(int i = m; i; i--) {ret[i] = id[i][Min];Min -= p[id[i][Min]]-d[id[i][Min]];}sort(ret+1, ret+1+m);for(int i = 1; i <= m; i++) {printf(" %d", ret[i]);}puts("");
}int main()
{kase = 0;while(scanf("%d%d", &n, &m) == 2) {if(!n && !m) return 0;read();dp();output();}return 0;
}