大佬留个赞吧

#include<bits/stdc++.h> using namespace std; struct l{ int v,w,m; }a[10000007]; int dp[10000007]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i].v>>a[i].w>>a[i].m; for(int i=1;i<=n;i++) for(int k=1;k<=a[i].m;k++) for(int j=m;j>=a[i].w;j--) dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v); cout<<dp[m]<<"\n"; return 0; }

题意分析 这是一道多重背包模板问题，但很显然，数据范围较大，实际运行会远超出我们的时间限制，因此我写了两种优化方案。 虽然ACGO神机1秒跑完1e9 朴素实现代码 思路极端暴力，将每种物品看作mim_imi 个相同物品，问题转化为01背包问题，时间复杂度O(nWM)O(nWM)O(nWM)，其中M=max(mi)M = max(m_i)M=max(mi )，分值为60。 二进制优化 数学思路，设有x∈[1,log⁡mi]x \in [1, \log m_i]x∈[1,logmi ]，尝试将2x2^x2x个物品看作一个整体，这些整体可以看作二进制的每一位并组成任何数量的物品，将剩余的mi−2xm_i-2^xmi −2x个物品单独处理，时间复杂度O(nWlog⁡M)O(nW\log M)O(nWlogM)，其中M=max(mi)M = max(m_i)M=max(mi )，分值为100。 滑动窗口优化 对于重量为www的物品，状态转移方程为：dp[j]=max⁡0≤k≤min⁡(m,⌊j/w⌋){dp[j−k⋅w]+k⋅v}dp[j] = \max_{0 \le k \le \min(m, \lfloor j/w \rfloor)} \{ dp[j - k \cdot w] + k \cdot v \}dp[j]=max0≤k≤min(m,⌊j/w⌋) {dp[j−k⋅w]+k⋅v} 按jmod  wj\mod wjmodw分组后，每组内是等差数列，可以用单调队列求滑动窗口最大值，理想时间复杂度O(nW)O(nW)O(nW)，实际会比二进制优化慢一些，分值为100。 估计是某个春竹又把memcpy当O(1)算错了 什么你问我为什么写这么多？ 为了尊重一下这道不优化多交几次就能过的绿题（ （滑动窗口优化方案来源于网络）