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