题解：UVA323 Jury Compromise

· · 题解

题目分析

这是一个有很多个维度的 01 背包。把 N 个候选人看作 N 个物品。那么，这 N 个物品有三种体积：

考虑按照人数划分阶段。当枚举完前 i 个人时，设 f_{j,d,p} 表示有 j 个人进入陪审团，当前辩方总分 d，控方总分 p 的状态是否可行，则：

f_{j,d,p} = f_{j,d,p}\ or\ f_{j-1,d-d_i,p-p_i}

初始时 f_{0,0,0} = 1，其余的为 0。目标是找到一个状态 f_{M,D,P}，使得 f_{M,D,P} = 1，且 \left|D-P\right| 尽量小，\left|D-P\right| 相同时 D+P 尽量大。

但是这种方法没有很好的利用 dp 中“价值”这一维度。事实上，可以把控方辩方的分差 d_i - p_i 作为物品的体积之一，把控方辩方的分数和 d_i + p_i 作为物品的价值。

设 f_{i,j,k} 表示前 i 个人中有 j 个人进入了陪审团，此时辩方总分和控方总分的差为 k 时，辩方总分和控方总分的和的最大值，则：

f_{i,j,k} = \max(f_{i - 1,j,k},f_{i - 1,j - 1,k - (d_i - p_i)} + d_i + p_i)

初始时 f_{0,0,0} = 0，其余为负无穷。目的是找到一个 f_{N,M,K}，使得 |k| 尽量小，当 |k| 相同时 f_{N,M,K} 尽量大。

值得注意的是，k 可能为负数，在实现时需要给 k 加上一个固定值。

最后输出方案时，根据 (N,M,K) 不断往前推即可，具体见代码。

Code

#include <bits/stdc++.h>
namespace SXL {
    using std::max;
    constexpr int MAXN = 200;
    constexpr int MAXM = 20;
    constexpr int MAXK = 800;
    constexpr int pyl = 400;
    int n,m;
    int d[MAXN + 5],p[MAXN + 5];
    int f[MAXN + 5][MAXM + 5][MAXK + 5];
    int tot;
    int cnt;
    int ans[MAXM + 5];
    void work() {
        memset(f,128,sizeof(f));
        tot = 0;
        for(int i = 1;i <= n;i++) {
            scanf("%d%d",d + i,p + i);
        }
        f[0][0][pyl] = 0;
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= m;j++) {
                for(int k = 0;k <= MAXK;k++) {
                    f[i][j][k] = f[i - 1][j][k];
                    int c = k - d[i] + p[i];
                    if(c < 0 || c > MAXK || j == 0) continue;
                    f[i][j][k] = max(f[i][j][k],f[i - 1][j - 1][c] + d[i] + p[i]);
                }
            }
        }
        int v = 0;
        while(f[n][m][pyl + v] < 0 && f[n][m][pyl - v] < 0) v++;
        if(f[n][m][pyl - v] > f[n][m][pyl + v]) v = pyl - v;
        else v = pyl + v;
        int i = n,j = m;
        while(i) {
            if(f[i][j][v] == f[i - 1][j][v]) {
                i--;
                continue;
            }
            ans[++tot] = i;
            v = v - d[i] + p[i];
            i--;
            j--;
        }
        int a1 = 0,a2 = 0;
        for(int i = 1;i <= tot;i++) {
            a1 += d[ans[i]];
            a2 += p[ans[i]];
        }
        printf("Jury #%d\n",++cnt);
        printf("Best jury has value %d for prosecution and value %d for defence:\n",a1,a2);
        for(int i = tot;i >= 1;i--) {
            printf(" %d",ans[i]);
        }
        puts("");
        puts("");
    }
    void main() {
        while(true) {
            scanf("%d%d",&n,&m);
            if(!n && !m) break;
            work();
        }
    }
}
int main() {
    SXL::main();
    return 0;
}