「BZOJ 1334」Elect - 背包 DP

N 个政党要组成一个联合内阁,每个党都有自己的席位数。现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好。对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的。

链接

BZOJ 1334

题解

一个显然的结论是,只要当席位最少的党是多余的,这个方案就一定不合法。

使用类似背包的方法,设 f(i) 表示联合内阁席位数为 i 时,席位最少的党的席位数的最大值。

完成 DP 后扫描整个数组,满足 i - f(i) \leq \frac{m}{2} 的最大的 i 即为答案。

代码

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 300;
const int MAXM = 100000;

int main() {
    int n;
    scanf("%d", &n);

    static int a[MAXN + 1];
    int m = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), m += a[i];

    static int f[MAXM + 1];
    f[0] = INT_MAX;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= a[i]; j--) {
            f[j] = std::max(f[j], std::min(f[j - a[i]], a[i]));
        }
    }

    int ans = 0;
    for (int i = m; i >= 0; i--) {
        if (i - f[i] <= m / 2) {
            ans = i;
            break;
        }
    }

    printf("%d\n", ans);

    return 0;
}