「BZOJ 1334」Elect - 背包 DP

发表于 | 分类于

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

链接

BZOJ 1334

题解

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

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

完成 DP 后扫描整个数组，满足 的最大的 即为答案。

代码

#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;
}