AcWing 6. 多重背包问题 III 对于偏移量的理解写了一点在注释
原题链接
困难
作者:
bnu001
,
2022-04-20 20:19:15
,
所有人可见
,
阅读 156
#include <bits/stdc++.h>
using namespace std;
const int N=20010;
int f[N],q[N],pre[N];
int n,m;
int main()
{
cin>>n>>m;
for (int i=0;i<n;i++)
{
memcpy(pre,f,sizeof f);//pre数组保存上一轮状况
int v,w,s;
cin>>v>>w>>s;
for (int j=0;j<v;j++)//这里枚举余数。每个余数对应一个队列。
{
int hh=0,tt=-1;
for (int k=j;k<=m;k+=v)
{
if (hh<=tt && k-s*v>q[hh]) hh++;
//k-s*v比队头还大,说明队里已经有超过s个元素了
//这时候队头就要弹出啦。
while (hh<=tt && pre[q[tt]]-q[tt]/v*w<=pre[k]-k/v*w) tt--;
/*
对于每一个元素,在每一轮循环的时候都要给它加上w,很麻烦
所以可以在更新的时候把若干个w再加上去
为了让更新的时候加上去的w个数都是“统一”的
在进队的时候我们就要把每个元素减去一些w来对齐
减去的数量就是k/v。就是枚举的轮数。
*/
if (hh<=tt) f[k]=max(f[k],pre[q[hh]]+(k-q[hh])/v*w);
/*
更新的时候,q[hh]那部分的应得的w个数已经在pre[q[hh]]里了
所以我们要加上(k-q[hh])/v*w
就大功告成了,真的很难理解呜呜呜TAT~
*/
q[++tt]=k;
}
}
}
cout<<f[m]<<endl;
return 0;
}