大致题意：
从n个候选人中选出m个人作为陪审团。为了让陪审团的选择更公平，辩方和控方都为这n个候选人给出了满意度（辩方为D[j]，控方为P[j]，范围0至20）.现在要使得选出的m位候选人的辩方总和与控方总和的差最小，如果有多个最小，选择辩方总和与空方总和的和最大的那个方案。
分析：
一开始以为就是普通的01背包，结果代码一写，WA了。后来发现|D[j]-P[j]|并不构成最优子结构，所以不是01背包。题目要我们求出的方案辩方总和与控方总和的差最小，并且在这个前提下，使得辩方总和和控方总和的和最大。这个是有优先顺序的。因为有这个优先顺序，动态就容易找了。
设dif[i]为辩控差，sum[i]为辩控和。d[j][k]表示，选了j个候选人，使得这j个候选人的辩控差为k，最大的辩控和。
动态转移方程：dp[j][k]=dp[j-1][k-dif[i]]+sum[i]
为了让k不为负，都加上m*20即可。
#include#include #include #include #include using namespace std;const int maxn=200+5;const int maxm=20+5;const int maxk=800+5;int dif[maxn],sum[maxn];int d[maxm][maxk];int p[maxm][maxk];int ans[maxm];int cnt;bool solve2(int index,int j,int k){ for(;j>0;k-=dif[p[j][k]],j--) if(p[j][k]==index) return false; return true;}int main(){ //freopen("in.txt","r",stdin); int n,m; int time=0; while(cin>>n>>m,n) { for(int i=1; i<=n; i++) { int D,P; scanf("%d%d",&D,&P); dif[i]=D-P; sum[i]=D+P; } memset(d,-1,sizeof(d)); memset(p,0,sizeof(p)); int fixed=m*20; d[0][fixed]=0; for(int j=1; j<=m; j++) for(int k=0; k<=fixed*2; k++) { int maxs=-1; for(int i=1; i<=n; i++) if(k-dif[i]>=0 && k-dif[i]<=fixed*2 && d[j-1][k-dif[i]]>=0 && solve2(i,j-1,k-dif[i]) && d[j-1][k-dif[i]]+sum[i]>maxs) { maxs=d[j-1][k-dif[i]]+sum[i]; p[j][k]=i; } d[j][k]=maxs; } int sum1=0,sum2=0,pos; for(int i1=fixed,i2=fixed; i1>=0; i1--,i2++) if(d[m][i1]>=0 || d[m][i2]>=0) { pos=i1; pos=d[m][i2]>d[m][i1]? i2:pos; break; } cnt=0; for(int j=m,k=pos;j>0;k-=dif[p[j][k]],j--) ans[cnt++]=p[j][k]; sort(ans,ans+cnt); for(int i=0; i