题解 | #【模板】多重背包#

单调队列优化的多重背包

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int __t = 1, n, m;
void solve() {
    cin >> n >> m;
    vector<int> w(n + 1), v(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i] >> s[i];
    vector<int> dp(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (w[i] == 0) {
            if (v[i] > 0) {
                for (int j = 0; j <= m; j++) {
                    dp[j] += s[i] * v[i];
                }
            }
            continue;
        }
        for (int j = 0; j < w[i]; j++) {
            deque<pair<int, int>> q;
            for (int k = 0; k <= (m - j) / w[i]; k++) {
                int val = dp[j + k * w[i]] - k * v[i];
                while (!q.empty() && q.back().second <= val) {
                    q.pop_back();
                }
                q.emplace_back(k, val);
                dp[j + k * w[i]] = q.front().second + k * v[i];
                if (q.front().first == k - s[i]) {
                    q.pop_front();
                }
            }
        }
    }
    cout << dp[m] << "\n";
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cin >> __t;
    while (__t--)
        solve();
    return 0;
}