单调队列优化
余数
算第i
个物品v时,每次更新k体积的背包时,即f[i][k]
每次更新,只会从f[i-1][k-0*v],f[i-1][k-v]+v,f[i-1][k-2v]+2v...f[i-1][k - sv]+sv ((k-sv) > 0))
.里选最大的更新,巧的是他们对模v
同余
所以我们可以枚举每个余数,各个不同余数的状态间更新互不影响
单调队列
物品数为3举例
f[i][k] = max( f[i-1][k]+(k-k), f[i-1][k-v]+(k-(k-v)), f[i-1][k-2v]+2v,f[i-1][k-3v]+3v)
f[i][k+v] = max(f[i - 1][k+v], f[i-1][k]+(k+v -k), f[i-1][k-v]+((k+v)-(k-v)), f[i-1][k-2v]+ 3v)
中间相同部分f[i][k+v]
的只比f[i][k]
的多v
,并不改变他们之间的相对大小,f[i][k+v]
更新时求max
时可以继续用
队列里记录的是f[i-1][k-nv]
的体积k-nv
,算的时候可以通过体积相减,把差的v
加回去
单调队列模型:定长队列,超队列长度值的出队,比新加入元素小的出队,剩余队内元素不变,和新加入元素比较时,每次通过体积差值比上一次用到时多加一个v
。
单调的是,队列里元素对于更新当前值的贡献大小
v当前体积,w当前物品价值
j j + v j + 2v ...... m
f[j]+(m-j)/v *w f[j+v]+(m-(j+v))/v * w f[j+2v]+(m-(j+2v))/v * w 让这些值用单调队列单调递减免于每次计算max
相对大小不变,更新m+v一样用,每个只比算m时大v
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int f[N], q[N];
int g[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
memcpy(g, f, sizeof g);
for (int j = 0; j < v; j ++)
{
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v)
{
while (hh <= tt && k - q[hh] > s * v) hh ++;
while (hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) tt --;
q[++ tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}