Sto flashhu orz flash太强啦
多重背包裸题(逃
使用压维大法,\(f_i\)为总重量为\(i\)时的答案
对于每种物品,记\(w\)为单个的重量,\(v\)为单个的价值,\(m\)为数量,列出转移方程$$f_i=min{f_{i-jw}+jv}(0\leq j\leq m,i-jw \geq 0)$$
数据范围较大,我们可以二进制优化
同样也可以用单调队列,令\(i=kw+b\)(按照余数分组)原方程可以变为$$f_i=min{f_{kw+b-jw}+(k+j-k)v}(...)$$$$=>\ f_i=min{f_{(k-j)w+b}-(k-j)v}+kv(...)$$
对于每个余数\(b\)转移,从后往前枚举\(k\),用单调队列维护长度为\(m\)的\(f_{(k-j)w+b}-(k-j)v\),如果队首超出范围就弹队首,然后用队首转移,然后维护队尾,插入当前元素一堆废话
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=40000+10;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL f[N],n,m,q[N][2],an;
int hd,tl;
int main()
{
n=rd(),m=rd();
while(n--)
{
LL v=rd(),w=rd(),p=rd();
for(re int b=0;b<w;b++)
{
int nn=(m-b)/w,i,j;
hd=1,tl=0;
for(i=nn-1;i>=max(nn-p,0);i--)
{
LL xx=f[i*w+b]-i*v;
while(hd<=tl&&xx>q[tl][0]) --tl;
q[++tl][0]=xx,q[tl][1]=i;
}
for(j=nn;j>=0;i--,j--)
{
while(hd<=tl&&q[hd][1]>=j) ++hd;
if(hd<=tl) f[j*w+b]=max(f[j*w+b],q[hd][0]+j*v);
if(i<0) continue;
LL xx=f[i*w+b]-i*v;
while(hd<=tl&&xx>q[tl][0]) --tl;
q[++tl][0]=xx,q[tl][1]=i;
}
}
}
for(int i=1;i<=m;i++) an=max(an,f[i]);
printf("%lld\n",an);
return 0;
}