题解 | 【模板】多重背包

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3005;

int T;
int n, m;
int w[N], v[N], s[N];
int dp[N];

inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i]>>s[i];
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){
        if(v[i] == 0) continue;
        if(w[i] == 0){
            for(int j=0;j<=m;j++) dp[j] = dp[j] + v[i]*s[i];
            continue;
        }
        for(int r=0;r<w[i];r++){
            deque<pair<int,int>> q;
            for(int j=r;j<=m;j+=w[i]){
                while(q.size() > 0 && j - q.front().first > w[i]*s[i]) q.pop_front();
                while(q.size() > 0 && dp[j] >= q.back().second + (j - q.back().first)/w[i]*v[i]) q.pop_back();
                q.push_back({j, dp[j]});
                dp[j] = max(dp[j], q.front().second + (j - q.front().first)/w[i]*v[i]);
            }
        }
    }
    cout<<dp[m]<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}