「BZOJ 4247」挂饰 - 背包 DP

发表于 | 分类于

JOI 君有 个装在手机上的挂饰，编号为 。JOI君可以将其中的一些装在手机上。

一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 个。此外，每个挂件有一个安装时会获得的喜悦值，用一个整数（可以为负）来表示。

JOI 君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

链接

BZOJ 4247

题解

允许背包容量为负，做一次背包，答案取背包容量为 到 时结果的最大值。

代码

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

const int MAXN = 2000;

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

    static struct Array {
        int a[MAXN * 2 + 1];
        int &operator[](const int i) { return a[i + MAXN]; }
    } f[MAXN + 1];

    for (int i = -n; i < 0; i++) f[0][i] = INT_MIN;

    for (int i = 1; i <= n; i++) {
        int x, v;
        scanf("%d %d", &x, &v);

        const int w = 1 - x;

        for (int j = -n; j <= n; j++) {
            if (j - w >= -n && j - w <= n && f[i - 1][j - w] != INT_MIN) f[i][j] = std::max(f[i - 1][j], f[i - 1][j - w] + v);
            else if (j - w > n) f[i][j] = std::max(f[i - 1][j], f[i - 1][n] + v);
            else f[i][j] = f[i - 1][j];
            // printf("f[%d][%d] = %d\n", i, j, f[i][j]);
        }
    }

    int ans = 0;
    for (int i = -n; i <= 1; i++) ans = std::max(ans, f[n][i]);

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

    return 0;
}