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

很坑，标记处的内个j非得从0开始，从一开始就过不去；

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> dp(m + 1);
    for (ll i = 1; i <= n; i++) {
        ll w, v; cin >> w >> v;
        ll s; cin >> s;
        if (w == 0) {
            for (ll j = 1; j <= m; j++) {////这儿
                dp[j] += s * v;
            }
            continue;
        }
        for (ll a = 0; a < w; a++) {
            deque<pair<ll, ll>> de;
            for (ll b = 0; a + b * w <= m; b++) {
                while (!de.empty() && de.back().first <= dp[a + b * w] - b * v)de.pop_back();
                de.push_back({ dp[a + b * w] - b * v, b });
                dp[a + b * w] = de.front().first + b * v;
                if (!de.empty() && de.front().second == b - s)de.pop_front();
            }
        }
    }
    cout << dp[m] << endl;
}