A29700 正经题解

题意分析
这是一道多重背包模板问题，但很显然，数据范围较大，实际运行会远超出我们的时间限制，因此我写了两种优化方案。
虽然ACGO神机1秒跑完1e9

朴素实现代码

#include <bits/stdc++.h>
using namespace std;
int n, W, v[105], w[105], m[105], dp[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> W;
    for(int i=1;i<=n;++i)
        cin >> v[i] >> w[i] >> m[i];
    for(int i=1;i<=n;++i){
        for(int k=1;k<=m[i];++k){
            for(int j=W;j>=w[i];--j){
                dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[W];

    return 0;
}

思路极端暴力，将每种物品看作$m_i$个相同物品，问题转化为01背包问题，时间复杂度$O(nWM)$，其中$M = max(m_i)$，分值为60。

二进制优化

#include <bits/stdc++.h>
using namespace std;

int n, W;
int dp[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> W;
    
    for(int i=1;i<=n;++i){
        int v, w, m;
        cin >> v >> w >> m;
        for(int k=1;k<=m;k*=2){
            int kv = k*v;
            int kw = k*w;
            for(int j=W;j>=kw;--j){
                dp[j] = max(dp[j], dp[j - kw] + kv);
            }
            m -= k;
        }
        if(m>0){
            int kv = m*v;
            int kw = m*w;
            for(int j=W;j>=kw;--j){
                dp[j] = max(dp[j], dp[j-kw]+kv);
            }
        }
    }
    
    cout << dp[W];
    return 0;
}

数学思路，设有$x \in [1, \log m_i]$，尝试将$2^x$个物品看作一个整体，这些整体可以看作二进制的每一位并组成任何数量的物品，将剩余的$m_i-2^x$个物品单独处理，时间复杂度$O(nW\log M)$，其中$M = max(m_i)$，分值为100。

滑动窗口优化

#include <bits/stdc++.h>
using namespace std;

int n, W;
int dp[100005], dp1[100005];
int q[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> W;
    for(int i=1;i<=n;++i){
        int v, w, m;
        cin >> v >> w >> m;
        memcpy(dp1, dp, sizeof(dp));
        for(int r=0;r<w;++r){
            int h=0, t=-1;
            for(int j=r;j<=W;j+=w){
                while(h<=t&&dp1[q[t]]-(q[t]-r)/w*v<=dp1[j]-(j-r)/w*v)
                    t--;
                q[++t] = j;
                while(h<=t&&(j-q[h])/w>m)
                    h++;
                if(h<=t){
                    int k = q[h];
                    dp[j] = max(dp[j], dp1[k]+(j-k)/w*v);
                }
            }
        }
    }
    
    cout << dp[W];
    return 0;
}

对于重量为$w$的物品，状态转移方程为：$dp[j] = \max_{0 \le k \le \min(m, \lfloor j/w \rfloor)} \{ dp[j - k \cdot w] + k \cdot v \}$
按$j\mod w$分组后，每组内是等差数列，可以用单调队列求滑动窗口最大值，理想时间复杂度$O(nW)$，实际会比二进制优化慢一些，分值为100。
估计是某个春竹又把memcpy当O(1)算错了

什么你问我为什么写这么多？
为了尊重一下这道不优化多交几次就能过的绿题（
（滑动窗口优化方案来源于网络）