poj1015 Jury Compromise 题解报告

题目传送门

【题目大意】

要从n个候选人中选出m人作为陪审团，对于这n个候选人，每个人都有两个分数，一个是辩护方的分数，一个是起诉方的分数。要求一种方案，使得辩护方分数之和与起诉方分数之和的差最小而和最大。求这种方案下辩护方分数和起诉方分数。

【思路分析】

我们可以把这道题目看做是具有多个“体积维度”的0/1背包问题。把n个候选人看做n个物品，那么每个物品有以下三种“体积”：

1.“人数”，每个候选人的“人数”体积都是1，最终要填满容积为m的背包

2.“辩方得分”，即辩方给候选人打的分数，记为a[i]

3.“控方得分”，即控方给候选人打的分数，记为b[i]

so我们依次考虑每个候选人是否进入陪审团，当考虑到第i个人时,f[j][d][p]表示已经有j个人被选入陪审团，当前辩方总分为d，控方总分为p的状态是否可行。$$f[j][d][p]=f[j][d][p]orf[j-1][d-a[i]][p-b[i]]$$初始值：f[0][0][0]=true，其余均为false。

目标：找到一个状态f[m][d][p]，满足f[m][d][p]=true，并且|d-p|最小，同时d+p最大。

接下来我们考虑一下如何优化，我们可以把|d-p|作为一个维度，并且用f[j][k]表示前i个人中选出j个，保证|d-p|等于k时d+p的最大值。

于是得到新的转移方程：$$f[j][k]=max(f[j][k],f[j-1][k-(a[i]-b[i])]+a[i]+b[i])$$初始值：f[0][0]=0，其余均为负无穷

目标：找到一个状态f[j][k]满足|k|尽量小，当|k|相同时f[j][k]尽量大。

在转移中要对j倒序循环，这样才符合0/1背包的特殊做法。

【代码实现】

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rg register
#define go(i,a,b) for(rg int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,dp[25][802];
int p[202],d[202],S[202],V[202];
int tag[25][802];
//tag[i][j]表示选了i个人分数为j时第i个人的编号
bool check(int a,int b,int c){//判断c是否被选过
    while(a>0&&c!=tag[a][b]){
        b-=V[tag[a][b]];a--;
    }
    return a;
}
int main(){
    int num=0;
    while(scanf("%d%d",&n,&m)){
        if(n==0&&m==0) break;
        go(i,1,n){
            scanf("%d%d",&p[i],&d[i]);
            S[i]=p[i]+d[i];
            V[i]=p[i]-d[i];
        }
        memset(dp,-1,sizeof(dp));
//dp[i][j]表示选了i个人使分数差值为j的最大和，如不存在则为-1
        memset(tag,0,sizeof(tag));
        int start=20*m;
        dp[0][start]=0;//相当于dp[0][0]
        go(i,1,m) go(j,0,2*start)
            if(dp[i-1][j]!=-1)
                go(k,1,n)
                    if(!check(i-1,j,k)&&dp[i][j+V[k]]<dp[i-1][j]+S[k]){
                        dp[i][j+V[k]]=dp[i-1][j]+S[k];
                        tag[i][j+V[k]]=k;
                    }
        int j;
        for(j=0;j<=start;j++)
            if(dp[m][start-j]!=-1||dp[m][start+j]!=-1) break;
        int sum=dp[m][start-j]>dp[m][start+j]?start-j:start+j;
        int P=(dp[m][sum]+sum-start)/2,D=(dp[m][sum]-sum+start)/2;
        printf("Jury #%d\n",++num);
        printf("Best jury has value %d for prosecution and value %d for defence:\n",P,D);
        int res[25];
        for(rg int i=0,j=m,k=sum;i<m;i++){
            res[i]=tag[j][k];
            k-=V[tag[j][k]];
            j--;
        }
        sort(res,res+m);
        go(i,0,m-1) printf(" %d",res[i]);
        puts("");puts("");
    }
    return 0;
}