第一次做dp分组的问题，百度的~~
http://poj.org/problem?id=1015
题目大意：在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。
2 2
1 2
3 4
大概思路如下。
设dp[i][j]表示选i个人，当前的差值是j的时候，最大的和值是dp[i][j]
由于他是abs的，这样会产生相同的j。但是应该分开的，因为路径是不同的，产生的dp[i][j]那个值不应该被其他覆盖。
然后就是记录路径，
path[i][j]表示是由那个值进化而来的，即可说是上一个，也可以说是这个的值。
然后思路就是，
枚举i : 1 to m //选m个人
k : 0 to 2 * fix //枚举差值。
判断即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int fix = ;
int dp[][]; // dp[i][j]表示选了i个人，差值为j的时候，的最大和值
int path[][];
int D[ + ];
int P[ + ];
int sum[ + ];
int dis[ + ];
set<int>ans;
int n, m;
void init() {
memset(dp, -, sizeof dp);
memset(path, -, sizeof path);
ans.clear();
}
void work() {
init();
for (int i = ; i <= n; ++i) {
cin >> D[i] >> P[i];
dis[i] = D[i] - P[i];
sum[i] = D[i] + P[i];
}
dp[][fix] = ; //因为fix了，所以0的时候，其实就是fix的时候
for (int i = ; i <= m; ++i) {
for (int k = ; k <= * fix; ++k) {
if (dp[i - ][k] >= ) { //如果这个状态可行，才能再选举一个人进来
for (int j = ; j <= n; ++j) {
if (dp[i - ][k] + sum[j] > dp[i][k + dis[j]]) { //加了这个人后，最优解变大，然后差值就是变成k + dis[j]的
//还需要检查j是否在dp[i - 1][k]这个路径上了。
int t = path[i - ][k];
int pre = i - ;
int ff = k;
bool flag = true;
while (t != -) {
if (t == j) {
flag = false;
break;
}
ff -= dis[t]; //减去当前这个点的值
t = path[--pre][ff];
}
if (flag == true) {
dp[i][k + dis[j]] = dp[i - ][k] + sum[j];
path[i][k + dis[j]] = j;
}
}
}
}
}
}
int i = fix;
int j = ;
while (dp[m][i + j] < && dp[m][i - j] < ) { //排除没用的状态
++j;
}
int KK; //最小的差值 对应的那个dp，可以对应输出最大的和值
if (dp[m][i + j] > dp[m][i - j]) {
KK = i + j;
} else KK = i - j;
int t = path[m][KK];
int pre = m;
int ff = KK;
while (t != -) {
ans.insert(t);
ff -= dis[t];
t = path[--pre][ff];
}
int df = , pf = ;
for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) {
df += D[*it];
pf += P[*it];
}
static int gg = ;
printf("Jury #%d\n", ++gg);
printf("Best jury has value %d for prosecution and value %d for defence:\n", df, pf);
for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) {
cout << " " << *it;
}
cout << endl << endl;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
IOS;
while (cin >> n >> m && (n + m)) {
work();
}
return ;
}