题意：
在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：
控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总 分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。思路：详见代码
1 #include2 #include 3 #include 4 #include 5 #define clc(a,b) sizeof(a,b,sizeof(a)) 6 #define LL long long 7 #include 8 using namespace std; 9 int p[1010],d[1010];10 int f[25][4010];//选i个人评审差为j时，评审和最大值。转移方程：f[i][j]=f[i-1][x]+d[k]+p[k];且x+p[k]-d[k]=j;{f[i-1][x]}满足条件的最大值.11 int path[25][4010];//记录i个人评审差为j,这种情况下的前一个人i-1是谁;12 int ans[25];13 int main() {14 // freopen("in.txt","r",stdin);15 int n,m;16 int grade;17 int casee=0;18 while(scanf("%d%d",&n,&m),n||m) {19 casee++;20 for(int i=1; i<=n; i++) {21 scanf("%d%d",&p[i],&d[i]);22 }23 // clc(f,-1);24 // clc(path,0);25 memset(f,-1,sizeof(f));26 memset(path,0,sizeof(path));27 grade=m*20;//避免下标为负,所以推广到零以上28 f[0][grade]=0;//初始化条件29 for(int i=0; i<=m; i++) {30 for(int j=0; j<=grade*2; j++) {31 if(f[i][j]>=0) {32 for(int k=1; k<=n; k++) {33 if(f[i][j]+d[k]+p[k]>f[i+1][j+p[k]-d[k]]) {34 int t1=i,t2=j;35 while(t1>0&&path[t1][t2]!=k) {36 t2-=p[path[t1][t2]]-d[path[t1][t2]];37 t1--;38 }//判断k是不是前面已经选过了39 if(t1==0) {40 f[i+1][j+p[k]-d[k]]=f[i][j]+d[k]+p[k];41 path[i+1][j+p[k]-d[k]]=k;42 }43 }44 }45 }46 }47 }48 int i=grade;49 int j=0;50 int k;51 // printf("%d\n",f[m][42]);52 while(f[m][i+j]<0&&f[m][i-j]<0) {53 j++;54 }//选出评审分绝对值最小55 if(f[m][i+j]>f[m][i-j])56 k=i+j;57 else58 k=i-j;59 printf("Jury #%d\n",casee);60 printf("Best jury has value %d for prosecution and value %d for defence:\n",(k-grade+f[m][k])/2,(f[m][k]-k+grade)/2);61 for(i=1; i<=m; i++) {62 ans[i]=path[m+1-i][k];63 k-=p[ans[i]]-d[ans[i]];64 }65 sort(ans+1,ans+m+1);66 for(i=1; i<=m; i++) {67 printf(" %d",ans[i]);68 }69 printf("\n\n");70 }71 }