陪审团

AcWing-280-陪审团

分析

见《进阶指南》第278页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210, M = 810, offset = 400;
int n, m;
int p[N], d[N];
int f[N][22][M], res[N];

int main () {
    int T = 0;
    while (scanf("%d%d", &n, &m), n || m) {
        for (int i = 1; i <= n; ++ i) scanf("%d%d", &p[i], &d[i]);

        memset(f, -0x3f, sizeof(f));
        f[0][0][offset] = 0;
        for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= m; ++ j)
        for (int k = 0; k < M; ++ k) {
            f[i][j][k] = f[i - 1][j][k];
            int val = k - (p[i] - d[i]);
            if (0 <= val && val < M && j >= 1)
                f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][val] + p[i] + d[i]);
        }

        int val = 0;
        while (f[n][m][offset - val] < 0 && f[n][m][offset + val] < 0) ++ val;
        val = f[n][m][offset - val] > f[n][m][offset + val] ? offset - val : offset + val;

        int i = n, j = m, k = val, idx = 0;
        while (j >= 1) {
            if (f[i][j][k] == f[i - 1][j][k]) {
                -- i;
            } else {
                res[++ idx] = i;
                k -= p[i] - d[i];
                -- i;
                -- j;
            }
        }
        int sp = 0, sd = 0;
        for (int i = 1; i <= idx; ++ i) {
            sp += p[res[i]];
            sd += d[res[i]];
        }
        printf("Jury #%d\n", ++ T);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);
        for (int i = idx; i >= 1; -- i) printf(" %d", res[i]);
        printf("\n\n");
    }
    return 0;
}