题意：n个陪审团，每个陪审团有x,y值，选出m个陪审团，要求 （sum（xi）-sum（yi））最少，当 （sum（xi）-sum（yi））最少有多个，取sum（xi）+sum（yi）最大那个
，并顺序输出陪审团的序号
思路：先x-y,x+y存起来，再按当dp[i][j]，j相同时，要值最大，当然存路径是最烦的。
#include <iostream>
#include<cstdio>
#include <cstring>
#include<algorithm>
using namespace std;
#define N 210
int path[25][1000],map[25][1000],n,m,sub[25*10],plusa[25*10],size,ans[25];
int main(int argc, char** argv) {
int i,j,k,x,y,cas=1;
while(scanf("%d%d",&n,&m)!=EOF,n||m){
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
sub[i]=x-y;
plusa[i]=x+y;
}
memset(map,-1,sizeof(map));
memset(path,-1,sizeof(path));
size=25*m;
map[0][size]=0;
path[0][size]=0;
for(i=1;i<=n;i++){
if(map[1][size+sub[i]]<plusa[i]){
map[1][size+sub[i]]=plusa[i];
path[1][size+sub[i]]=i;
}
}
for(i=1;i<m;i++){
for(j=0;j<2*size;j++)
if(path[i][j]>=0){
for(k=1;k<=n;k++){
if(map[i+1][j+sub[k]]<map[i][j]+plusa[k]){
for(x=i,y=j;x>=1;x--){
if(path[x][y]==k)
break;
y-=sub[path[x][y]];
}
if(x<1){
map[i+1][j+sub[k]]=map[i][j]+plusa[k];
path[i+1][j+sub[k]]=k;
}
}
}
}
}
int num=0;
for(i=0;i<=2*size;i++){
if(map[m][size+i]>=0||map[m][size-i]>=0){
if(map[m][size+i]>map[m][size-i])
j=size+i;
else
j=size-i;
break; }
}
for(i=m,k=j;i>=1;i--){
ans[num++]=path[i][k];
k-=sub[ans[num-1]];
}
sort(ans,ans+num);
printf("Jury #%d\n",cas++);
printf("Best jury has value %d for prosecution and value %d for defence: \n",(map[m][j]+j-size)/2,(map[m][j]-(j-size))/2);
for(i=0;i<num;i++){
printf(" %d",ans[i]);
}
printf("\n");
}
return 0;
}