1980:陪审团的人选
总时间限制:
1000ms
内存限制:
65536kB
描述
在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：
控 方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总
分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。
输入
输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1<=n<=200, 1<=m<=20 而且 m<=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有
效数据之间以空行分隔。最后一组数据n=m=0
输出
对每组数据，先输出一行，表示答案所属的组号,如 'Jury #1', 'Jury #2', 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。
样例输入
4 2
1 2
2 3
4 1
6 2
0 0
样例输出
Jury #1
Best jury has value 6 for prosecution and value 4 for
defence:
2 3
来源
Southwestern
European Regional Contest 1996, POJ 1015, 程序设计实习2007
【思路】
DP。
设d[i][j]表示该选第i个人且辩方与控方之差为j时最大的辩控和。
设P为辩方分数D为控方分数，v(i)=P[i]-D[i],S(i)=P[i]+D[i]
有如下转移式：
d[i][j]=max{ d[i-1][j-v(k)]+S(k) }
转移式表示第i个人选k，且k必须要满足在d[i-1][j-v(k)]的最优选择中没有出现过。
用path[i][j]记录差值为j时所选的第i个人，一方面检查k是否出现过，一方面方便构造解。
差值会为负值因此将差值全部偏移N个单位。
【代码】
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn = +; int d[][*maxn];
int path[][*maxn];
int P[maxn],D[maxn]; int n,m;
vector<int> ans; int main() {
ios::sync_with_stdio(false);
int kase=;
while(cin>>n>>m && (n&&m)) {
for(int i=;i<=n;i++) cin>>P[i]>>D[i];
memset(d,-,sizeof(d));
memset(path,,sizeof(path));
int N=m*;
d[][N]=;
for(int i=;i<m;i++) {
for(int j=;j<=*N;j++) if(d[i][j]>=)
{
for(int k=;k<=n;k++) {
if(d[i][j]+P[k]+D[k]>d[i+][j+P[k]-D[k]]) {
int ti=i,tj=j;
while(ti> && path[ti][tj]!=k) {
tj-=P[path[ti][tj]]-D[path[ti][tj]];
ti--;
}
if(!ti) {
d[i+][j+P[k]-D[k]]=d[i][j]+P[k]+D[k];
path[i+][j+P[k]-D[k]]=k;
}
}
}
}
}
int i=N,j=,k,totP=,totD=;
while(d[m][i+j]<&&d[m][i-j]<) j++;
if(d[m][i+j]>d[m][i-j]) k=i+j;
else k=i-j;
ans.clear();
for(i=;i<=m;i++)
{
ans.push_back(path[m-i+][k]) ;
k-=P[ans[i-]]-D[ans[i-]];
totP += P[ans[i-]]; totD += D[ans[i-]];
}
sort(ans.begin(),ans.end());
printf("Jury #%d\n",++kase);
printf("Best jury has value %d for prosecution and value %d for defence:\n",totP,totD);
for(i=;i<m;i++)
printf(" %d",ans[i]);
printf("\n\n");
}
return ;
}