poj1015 Jury Compromise

/*    直接上翻译吧    这是一道动态规划，请教了wmy学姐之后感觉有思路了    感觉和二维费用背包有点像    需要考虑的方面有 控辩和，控辩差，人数，组合路径    其中路径可以另外设一个path[i][j]表示使得[i][j]这个状态最优的上一个是谁    dp[i][j]=k表示选了i个人，总的控辩差是j的总控辩和是多少    最后找答案时只需找最接近需求值的j所对应的路径以及总控辩和差*/#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define maxn 205#define maxm 25int dp[maxm][maxn*10],path[maxm][maxn*10],n,m,a[maxn],b[maxn],Ans[maxn];bool vis[220];void up(int i,int j){    memset(vis,0,sizeof(vis));    while(path[i][j]!=-1){        int k=path[i][j];        vis[k]=1;        i--;j-=a[k]-b[k];    }}void update(int i,int j,int k){    int x=a[k]+b[k];    int y=a[k]-b[k];    if(dp[i+1][j+y]==-1||(dp[i+1][j+y]<dp[i][j]+x)){        dp[i+1][j+y]=dp[i][j]+x;        path[i+1][j+y]=k;    }}int main(){    int T=0;    while(scanf("%d%d",&n,&m),n|m){        memset(dp,-1,sizeof(dp));        memset(path,-1,sizeof(path));        memset(a,0,sizeof(a));        memset(b,0,sizeof(b));        memset(Ans,0,sizeof(Ans));        T++;        printf("Jury #%d \n",T);        for(int i=0;i<n;i++)scanf("%d%d",&a[i],&b[i]);        int w=20*m;        dp[0][w]=0;        for(int i=0;i<m;i++)for(int j=0;j<=w*2;j++)            if(dp[i][j]!=-1){                up(i,j);                for(int k=0;k<n;k++)                    if(!vis[k])update(i,j,k);            }        int d1=-1,d2=-1,ans;        for(int i=0;i<=w;i++)            if(dp[m][w+i]!=-1){d1=i;break;}        for(int i=0;i<=w;i++)            if(dp[m][w-i]!=-1){d2=i;break;}        if(d1==-1||(d1>d2&&d2!=-1))ans=w-d2;        else if(d2==-1||(d1<d2&&d1!=-1))ans=w+d1;        else if(d1==d2&&dp[m][w+d1]>dp[m][w-d2])ans=w+d1;        else ans=w-d2;        int x=dp[m][ans],y=ans-w;         int ans1=(x+y)/2,ans2=(x-y)/2;        printf("Best jury has value %d for prosecution and value %d for defence:\n", ans1, ans2);        int cnt=0;        int u=m,v=ans;        while(path[u][v]!=-1){            int k=path[u][v];            Ans[cnt++]=k;            u--;v-=a[k]-b[k];        }        sort(Ans,Ans+cnt);        for (int i = 0; i < cnt; i++)        printf(" %d", Ans[i] + 1);        putchar(‘\n‘);        putchar(‘\n‘);    }    return 0;}