单调队列（单调栈）优化 DP
引入
单调队列主要用于维护两端指针单调不减的区间最值，而单调栈则主要用于维护前/后第一个大于/小于当前值的数。
注意
- 求最小值要维护 单调递增/不减 的单调队列/单调栈，反之亦然。
- 维护单调递增/递减比较时用 小于等于/大于等于，维护单调不减/不增比较时用 小于/大于。
单调队列优化具体步骤
- 加入所需元素：向单调队列重复加入元素直到当前元素达到所求区间的右边界，这样就能保证所需元素都在单调队列中。
- 弹出越界队首：单调队列本质上是维护的是所有已插入元素的最值，但我们想要的往往是一个区间最值。于是我们弹出在左边界外的元素，以保证单调队列中的元素都在所求区间中。
- 获取最值：直接取队首作为答案即可。
单调栈优化具体步骤
- 弹出非法栈顶：通过比较当前元素与栈顶的大小，弹出不满足单调栈性质的栈顶。以单调递增的栈（即栈顶最大，维护最小值）为例，将所有大于等于当前元素的栈内元素全部弹出。
- 加入当前元素：将当前元素入栈即可。
单调队列优化多重背包
P1776 宝物筛选
你有 \(n\) 个物品，每个物品重量为 \(v_i\)，价值为 \(w_i\)，数量为 \(c_i\)。你有一个承重上限为 \(m\) 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。
设 \(f_{i,j}\) 表示前 \(i\) 个物品装入承重为 \(j\) 的背包的最大价值，朴素的转移方程为
\[
f_{i,j}=\max_{k=0}^{c_i}\{f_{i-1,j-k\times v_i}+k\times w_i\}
\]
时间复杂度 \(O(m\sum c_i)\)。
这看起来无法优化，但注意到，对于每一个物品，转移一定相隔 \(v_i\) 的倍数，也就是说，转移一定在 \(f_{i, d}, f_{i, d + v_i}, f_{i, d + 2v_i}, ..., f_{i, d + k \times v_i}\) 之间进行。
由此为出发点，我们枚举这个 \(d\)（它实际上是当前容量模 \(v_i\) 的结果），改写转移方程：
\[
\begin{aligned}
f_{i, d + j \times v_i} &= \max_{0 \leq j - k \leq c_i}\{f_{i - 1, d + k \times v_i} + (j - k) \times w_i\} \\
&= \max_{j - c_i \leq k \leq j}\{f_{i - 1, d + k \times v_i} - k \times w_i\} + j \times w_i
\end{aligned}
\]
这样就可以单调队列优化了，每次转移就是 \(O(d) \times O(\lfloor\frac{m}{d}\rfloor) = O(m)\) 的，总复杂度为 \(O(nm)\)。
显然可以滚动数组优化。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | |