题目描述

blablabla

样例

blablabla

题解

其实就是把几个背包合在了一起
开一个数组记录这个物品需要做01背包还是完全背包，因为01背包和完全背包的循环方式不同

C++ 代码

#include <bits/stdc++.h>
const int maxn = 5e5 + 100;
typedef long long LL;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

int n;
int m;
int size;
int v[maxn];
int w[maxn];
int k[maxn];
int f[maxn];

int main() {
    size = 0;
    read(n), read(m);
    for (int i = 1, x, y, z, t; i <= n; ++i) {
        read(x), read(y), read(z);
        if (z < 0) { w[++size] = x, v[size] = y; k[size] = 1; }
        else if (z == 0) { w[++size] = x, v[size] = y; k[size] = 0; }
        else if (z > 0) {
            t = 1;
            while (t <= z) {
                w[++size] = x * t;
                v[size] = y * t;
                k[size] = 1;
                z -= t;
                t <<= 1;
            }
            w[++size] = x * z;
            v[size] = y * z;
            k[size] = 1;
        }
    }

    f[0] = 0;
    for (int i = 1; i <= size; ++i) {
        if (k[i])
            for (int j = m; j >= w[i]; --j)
                f[j] = std::max(f[j], f[j - w[i]] + v[i]);
        else
            for (int j = w[i]; j <= m; ++j)
                f[j] = std::max(f[j], f[j - w[i]] + v[i]);
    }

    printf("%d\n", f[m]);
    return 0;
}