题意

多重背包

数据范围：$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$

题解

设$w$为价值，$v$为体积，$c$为数量
多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$
由于$i$一定从$i-1$转移而来，所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$
但是这样$dp$的复杂度为$O(N^3)$，需要进行优化
发现在计算$f[j]$与$f[j-v]$重复使用了较多的相同状态；而对于所有模$v$同余的$j$都存在这个问题
那么按模$v$划分：令$j=pv+d$，则

$$ \begin{aligned} f[j] &=\max(f[pv+d-kv]+kw) \\ &=\max(f[(p-k)v+d]+kw) \\ &=\max(f[(p-k)v+d]-(p-k)w)+pw \\ \end{aligned} $$

为了方便描述，将$p-k$换原为$k$
$$f[j]=\max(f[kv+d]-kw)+pw$$
其中$k \in [0,p)$
这样便可以使用单调队列优化
具体操作为：枚举每个$d$（余数），然后对于每$d$都用单调队列优化即可

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=4e4+10;
int n,m,w,v,c;
int hd,tl,sum;
int dp[M],mq[M],id[M];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&w,&v,&c);
        if(v==0){ //v=0时特殊处理
            sum+=w*c;
            continue;
        }
        int p=m/v;
        c=min(c,p);
        for(int d=0;d<v;d++){
            hd=1,tl=0;
            for(int k=0;k<=p;k++){
                int t=dp[k*v+d]-k*w;
                for(;hd<=tl && t>=mq[tl];tl--);
                mq[++tl]=t;
                id[tl]=k;
                for(;hd<=tl && id[hd]<k-c;hd++);
                dp[k*v+d]=max(dp[k*v+d],mq[hd]+k*w);
            }
        }
    }
    printf("%d",dp[m]+sum);
    return 0;
}