单调队列优化多重背包

朴素：
$$ f_{j}\gets\max\{f_j,f_{j-v},f_{j-2v},f_{j-3v},\cdots,f_{j-sv}\}(假设\,j\ge sv) $$

1
2
3
4

0		1		2		3 ... v - 1
v v+1 v+2 v+3

j j+1 j+2 ...  m

1
2
3
4
5

q v+q 2v+q 3v+q ... pv+q

dp[j]    =max(dp[j])
dp[j + v]=max(dp[j + v] - w, dp[j]) + w
dp[j +2v]=max(dp[j +2v] - 2w, dp[j + v] - w, dp[j]) + 2w

dp[j+kv] 在队列中的实际应为 dp[j+kv]-kw

现在已知是第 $i$ 个物品，同余类为 $j$，体积为 $k=j+xv$

$x=\dfrac{k-j}{v}$

$dp(k)-\dfrac{k-j}{v}w$

假设单调队列中最大值为 $a=j+yv$，最后的 $b=j+zv$

判断出队：

$k-a=(x-y)v$

要求 $x-y>s$

那么 $k-a>sv$

$dp(j+yv)-yw+\dfrac{k-j}{v}w$

$a=j+yv$

$y=\dfrac{a-j}{v}$

$dp(a)+\dfrac{k-a}{v}w$