HDU POJ 1015 Jury Compromise（陪审团的人选，DP）

题意：

在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：
控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总
分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。

思路：详见代码

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #define clc(a,b) sizeof(a,b,sizeof(a))

 #define LL long long

 #include<cmath>

 using namespace std;

 int p[],d[];

 int f[][];//选i个人评审差为j时，评审和最大值。转移方程：f[i][j]=f[i-1][x]+d[k]+p[k];且x+p[k]-d[k]=j;{f[i-1][x]}满足条件的最大值.

 int path[][];//记录i个人评审差为j,这种情况下的前一个人i-1是谁;

 int ans[];

 int main() {

 //    freopen("in.txt","r",stdin);

     int n,m;

     int grade;

     int casee=;

     while(scanf("%d%d",&n,&m),n||m) {

         casee++;

         for(int i=; i<=n; i++) {

             scanf("%d%d",&p[i],&d[i]);

         }

 //        clc(f,-1);

 //        clc(path,0);

         memset(f,-,sizeof(f));

         memset(path,,sizeof(path));

         grade=m*;//避免下标为负,所以推广到零以上

         f[][grade]=;//初始化条件

         for(int i=; i<=m; i++) {

             for(int j=; j<=grade*; j++) {

                 if(f[i][j]>=) {

                     for(int k=; k<=n; k++) {

                         if(f[i][j]+d[k]+p[k]>f[i+][j+p[k]-d[k]]) {

                             int t1=i,t2=j;

                             while(t1>&&path[t1][t2]!=k) {

                                 t2-=p[path[t1][t2]]-d[path[t1][t2]];

                                 t1--;

                             }//判断k是不是前面已经选过了

                             if(t1==) {

                                 f[i+][j+p[k]-d[k]]=f[i][j]+d[k]+p[k];

                                 path[i+][j+p[k]-d[k]]=k;

                             }

                         }

                     }

                 }

             }

         }

         int i=grade;

         int j=;

         int k;

 //        printf("%d\n",f[m][42]);

         while(f[m][i+j]<&&f[m][i-j]<) {

             j++;

         }//选出评审分绝对值最小

         if(f[m][i+j]>f[m][i-j])

             k=i+j;

         else

             k=i-j;

         printf("Jury #%d\n",casee);

         printf("Best jury has value %d for prosecution and value %d for defence:\n",(k-grade+f[m][k])/,(f[m][k]-k+grade)/);

         for(i=; i<=m; i++) {

             ans[i]=path[m+-i][k];

             k-=p[ans[i]]-d[ans[i]];

         }

         sort(ans+,ans+m+);

         for(i=; i<=m; i++) {

             printf(" %d",ans[i]);

         }

         printf("\n\n");

     }

 }