OI-wiki 单调队列 / 单调栈优化 DP 完全指南从区间最值加速到多重背包与滑动窗口问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 中「单调队列 / 单调栈优化 DP」专题的技术解读围绕 docs/dp/opt/monotonic-queue-stack.md 展开。单调队列与单调栈是动态规划DP中最基础、最高频的一类转移优化工具当状态转移依赖「一段连续区间上的最值」时它们能把单次转移从 $O(n)$ 摊还到 $O(1)$。读完本文你将掌握单调队列 / 单调栈的维护规则与三步操作流程、如何把朴素多重背包从 $O(W\sum k_i)$ 优化到 $O(nW)$以及如何用单调队列把「区间最大值转移型」DP以 CF372C 为例优化到 $O(nm)$并看懂仓库中对应的完整可运行 C 实现。引入为什么 DP 需要单调队列 / 单调栈很多 DP 的状态转移可以写成「当前状态 某个函数前一段连续状态的最值 代价」的形式。直接枚举前驱状态单次转移是 $O(n)$ 的整体往往无法承受。而单调队列与单调栈正是为了高效维护「滑动窗口内的最值」而生的线性数据结构。在 OI-wiki 的体系里这两个结构的前置知识分别是单调队列本质上是一个「单调 双端操作」的结构元素只能从队头、队尾进出STL 中对应deque主要用于维护两端指针单调不减的区间最值单调栈满足单调性的栈结构只在一端进出主要用于维护前 / 后第一个大于 / 小于当前值的数。一句话区分单调队列管「任意区间的最值」单调栈管「左右两边第一个更大 / 更小的数」。在做 DP 优化时绝大多数场景用的是单调队列单调栈则常在决策具有某种单调性如下一个更小元素、贡献栈时登场。从 DP 优化方法总览docs/dp/opt/dp-opt.md的分类看单调队列 / 单调栈优化属于「利用常见技巧优化」这一大类它适用的典型转移形如$$ f(i) F(a_i, {f(j) : j i}), $$即当前状态依赖于前一段状态上的区间最值等信息此时维护一个单调队列 / 单调栈即可把每次转移加速到均摊 $O(1)$。一个容易出错的细节使用单调结构求最值时有一个必须牢记的对应关系求最小值要维护单调递增 / 不减的单调队列 / 单调栈求最大值要维护单调递减 / 不增的单调队列 / 单调栈。另一个细节是关于比较符号的选取维护单调递增 / 递减严格单调时比较用小于等于 / 大于等于即把相等元素也弹出保证严格单调维护单调不减 / 不增时比较用小于 / 大于相等元素保留。这两条规则直接决定维护出的结构是严格单调还是允许相等进而影响正确性务必在写代码前先确定清楚。单调队列优化三步操作流程单调队列优化 DP 的通用步骤可以归纳为三步这也是 单调队列 中「滑动窗口」思想的直接推广加入所需元素向单调队列重复加入元素直到当前元素达到所求区间的右边界。这样能保证所需元素都在单调队列中弹出越界队首单调队列维护的是「所有已插入元素」的最值而我们想要的是「某个区间」的最值因此要弹出在左边界外的元素保证队列中元素都在所求区间内获取最值直接取队首作为答案。三步法对应到代码上就是经典的「入队 → 弹出过期队头 → 取队头」结构。其正确性依赖一个关键事实每个元素最多入队一次、出队一次因此整体复杂度为 $O(n)$。单调栈优化两步操作流程单调栈的维护更简单只有两步弹出非法栈顶通过比较当前元素与栈顶的大小弹出不满足单调栈性质的栈顶。以「单调递增的栈」栈顶最大、维护最小值为例需要将所有大于等于当前元素的栈内元素全部弹出加入当前元素将当前元素入栈。在 docs/ds/monotonic-stack.md 中给出了插入的伪代码insert x while !sta.empty() sta.top()x sta.pop() sta.push(x)单调栈在 DP 中的经典用途包括计算每个位置左右两侧第一个比它大 / 小的元素位置从而把「以每个位置为最值的区间贡献」在 $O(n)$ 内算出、离线解决 RMQ 问题按右端点排序扫描栈上第一个位置 $\ge l$ 的元素即答案可用二分加速等。实战一单调队列优化多重背包问题描述与朴素方程题目有 $n$ 个物品第 $i$ 个物品重量为 $w_i$价值为 $v_i$数量为 $k_i$背包承重上限为 $W$求不超过重量上限时可获得的最大价值。若未系统学习过背包 DP可先阅读 背包 DP。设 $f_{i,j}$ 表示前 $i$ 个物品装入承重为 $j$ 的背包的最大价值朴素转移方程为$$ f_{i,j}\max_{k0}^{k_i}(f_{i-1,j-k\times w_i}v_i\times k) $$直接计算的时间复杂度为 $O(W\sum k_i)$当物品数量与单件数量都很大时不可接受。数学变形把多重背包变成区间最值核心观察是同一物品只会从「模 $w_i$ 同余」的容量之间转移。按容量对 $w_i$ 取模分类设$$ g_{x,y}f_{i,x\times w_iy},\qquad g{x,y}f{i-1,x\times w_iy},\qquad 0\le yw_i, $$则转移方程改写为$$ g_{x,y}\max_{k0}^{k_i}(g_{x-k,y}v_i\times k) $$再引入$$ G_{x,y}g_{x,y}-v_i\times x $$方程化为$$ g_{x,y}\max_{k0}^{k_i}(G_{x-k,y})v_i\times x $$这就是经典的单调队列优化形式对固定的 $y$$\max_{k0}^{k_i}G_{x-k,y}$ 是「$G$ 数组中一个长度不超过 $k_i1$ 的滑动窗口最大值」完全可以用单调队列维护。复杂度分析$G_{x,y}$ 可 $O(1)$ 计算因此对固定的 $y$可以在 $O\left(\left\lfloor \dfrac{W}{w_i} \right\rfloor\right)$ 时间内算出所有 $g_{x,y}$而 $y$ 共有 $w_i$ 个取值故处理一个物品的复杂度为 $O(W)$。总复杂度从 $O(W\sum k_i)$ 降为$O(nW)$。实现要点与仓库源码在实现时需要注意必须先枚举 $y$余数类再枚举 $x$这样单调队列才能跨物品轮次复用单调队列中存储的是$x-k$即决策点的 $x$ 下标而不是 $k$ 本身使用队列元素时通过f[last][q.front() * w[i] y] - q.front() * v[i]还原 $G_{x-k,y}$ 的值由于 $x-k\in [x-k_i,,x]$枚举 $x$ 的过程中需要把队列中不在该范围内的元素弹出对应「弹出越界队首」。仓库中该专题的完整参考实现位于 docs/dp/code/opt/monotonic-queue-stack/monotonic-queue-stack_2.cpp核心循环如下已含注释#include array #include deque #include iostream constexpr int MAXV 4e4 10; constexpr int MAXN 1e2 10; using namespace std; int n, W, last 0, now 1; arrayint, MAXN v, w, k; arrayarrayint, MAXV, 2 f; // 滚动数组last 表示 i-1now 表示 i dequeint q; int main() { ios::sync_with_stdio(false); cin n W; for (int i 1; i n; i) { cin v[i] w[i] k[i]; } for (int i 1; i n; i) { for (int y 0; y w[i]; y) { // 先枚举余数 y // 清空队列 dequeint().swap(q); for (int x 0; x * w[i] y W; x) { // 弹出不在 [x - k[i], x] 范围内的元素过期队首 while (!q.empty() q.front() x - k[i]) { q.pop_front(); } // 保证队列单调递减比较 G 值弹出更差的队尾 while (!q.empty() f[last][q.back() * w[i] y] - q.back() * v[i] f[last][x * w[i] y] - x * v[i]) { q.pop_back(); } q.push_back(x); // G(队首) v[i] * x 即当前状态的最优值 f[now][x * w[i] y] f[last][q.front() * w[i] y] - q.front() * v[i] x * v[i]; } } swap(last, now); // 滚动数组轮换 } cout f[last][W] endl; return 0; }实现细节说明f使用两行滚动数组last/now处理完一个物品后swap(last, now)空间复杂度 $O(W)$内层队列存储的是 $x$ 下标比较时用f[last][idx * w[i] y] - idx * v[i]还原 $G$ 值做单调性维护这里维护的是递减队列队首即区间内 $G$ 的最大值对应求价值最大队首过期判定q.front() x - k[i]精确对应「数量限制 $k_i$」这一滑动窗口宽度。用仓库测试数据验证仓库为这份代码配套了输入输出样例docs/dp/examples/opt/monotonic-queue-stack/输入monotonic-queue-stack_2.in4 20 3 9 3 5 9 1 9 4 2 8 1 3表示 4 个物品、背包容量 20每个物品依次给出价值、重量、数量。期望输出monotonic-queue-stack_2.ans47你可以将上面的代码与本样例对照运行验证推导与实现的一致性——这正是 OI-wiki 每份代码都配套.in/.ans测试数据的用意。实战二CF372C Watching Fireworks is Fun题目与状态设计例题来自 CF372C Watching Fireworks is Fun城镇有 $n$ 个位置有 $m$ 个烟花依次燃放。第 $i$ 个烟花的燃放时间为 $t_i$、位置为 $a_i$若燃放时你处在位置 $x$则获得 $b_i-|a_i-x|$ 点快乐值。初始位置任意每个单位时间最多移动 $d$ 个单位距离求能获得的最大快乐值总和。设 $f_{i,j}$ 表示放第 $i$ 个烟花时你处在位置 $j$ 所能获得的最大快乐值。转移来源是上一个烟花时的位置 $k$而两个烟花之间可移动的距离上限为 $(t_i-t_{i-1})\times d$故$$ f_{i,j}\max{f_{i-1,k}b_i-|a_i-j|},\qquad j-(t_i-t_{i-1})\times d\le k\le j(t_i-t_{i-1})\times d $$变形为区间最值对转移方程做两次提常量变形$b_i$ 与 $k$ 无关提出$$ f_{i,j}\max{f_{i-1,k}-|a_i-j|}b_i $$确定 $i,j$ 后 $|a_i-j|$ 是常数再提出$$ f_{i,j}\max{f_{i-1,k}}-|a_i-j|b_i $$这样max只作用于上一状态的一段连续区间 $k\in[j-\Delta t\cdot d,;j\Delta t\cdot d]$其中 $\Delta tt_i-t_{i-1}$正是滑动窗口最大值问题。计算新一层的 $f_i$ 时只需把上一层的 $f_{i-1}$ 依次加入单调队列同时弹出越界队首即可均摊 $O(1)$ 获得 $\max{f_{i-1,k}}$。复杂度对每个烟花在每个位置上做一次入队 / 出队总时间复杂度 $O(nm)$。仓库源码实现完整参考代码在 docs/dp/code/opt/monotonic-queue-stack/monotonic-queue-stack_1.cpp#include algorithm #include cstring #include iostream using namespace std; using ll long long; constexpr int MAXN 150000 10; constexpr int MAXM 300 10; ll f[2][MAXN]; // 滚动数组f[fl][j] 表示当前烟花时位置 j 的最大快乐值 ll a[MAXM], b[MAXM], t[MAXM]; // 烟花位置、基础快乐值、燃放时间 int n, m, d; int que[MAXN]; // 手写数组模拟单调队列存位置下标 int fl 1; void init() { memset(f, 207, sizeof(f)); // 初始化为极小值0xCF... 即很大的负数 memset(que, 0, sizeof(que)); for (int i 1; i n; i) f[0][i] 0; // 第一个烟花前可任意站 fl 1; } void dp() { init(); for (int i 1; i m; i) { int l 1, r 0, k 1; // 单调队列队头/队尾指针 for (int j 1; j n; j) { // 把能转移到 j 的新决策点 k 加入单调队列 // 可移动范围j ± d * (t[i] - t[i-1]) for (; k min(1ll * n, j d * (t[i] - t[i - 1])); k) { while (l r f[fl ^ 1][que[r]] f[fl ^ 1][k]) r--; // 维护单调递减 que[r] k; } // 弹出越界队首位置太靠左无法转移到当前 j while (l r que[l] max(1ll, j - d * (t[i] - t[i - 1]))) l; // 队首即区间最大值决策点 f[fl][j] f[fl ^ 1][que[l]] - abs(a[i] - j) b[i]; } fl ^ 1; // 滚动数组轮换 } } int main() { cin n m d; for (int i 1; i m; i) cin a[i] b[i] t[i]; dp(); ll ans -1e18; for (int i 1; i n; i) ans max(ans, f[fl ^ 1][i]); cout ans endl; return 0; }实现要点这里用数组手写队列que[l..r]替代deque避免 STL 开销适合 $n$ 高达 $1.5\times 10^5$、$m$ 达 $300$ 的数据规模内层用k指针只进不退地加入新决策点每个位置在整个烟花轮次中恰好入队、出队各一次保证总复杂度 $O(nm)$队首过期条件que[l] max(1ll, j - d * (t[i] - t[i - 1]))正是「弹出越界队首」步骤窗口宽度由移动距离决定。仓库配套样例docs/dp/examples/opt/monotonic-queue-stack/monotonic-queue-stack_1.in50 3 1 49 1 1 26 1 4 6 1 10期望输出monotonic-queue-stack_1.ans-31注意答案可以是负数快乐值公式中存在 $-|a_i-j|$ 项且初始化为极小值这说明ans初始化时必须使用足够小的值代码中为-1e18这也是这类「区间最值转移型 DP」常见的边界陷阱。更多习题与复杂度总结单调队列 / 单调栈优化 DP 在竞赛中应用极广原文档还给出了以下进阶习题「Luogu P1886」滑动窗口单调队列最经典的模板题也是本专题一切结论的起点「NOI2005」瑰丽华尔兹在网格上按方向分段做单调队列优化 DP 的经典应用「SCOI2010」股票交易把买卖限制建模为带数量上限的转移同样可用单调队列优化。最后把本专题的核心结论汇总如下场景维护结构关键操作复杂度定长 / 变长滑动窗口最值单调队列加入元素、弹出越界队首、取队首$O(n)$ 摊还左右第一个更大 / 更小元素单调栈弹出非法栈顶、入栈$O(n)$ 摊还多重背包数量上限 $k_i$单调队列按余数 $y$ 分组窗口宽度为 $k_i1$ 的区间最值$O(nW)$区间最值转移型 DP如 CF372C单调队列每层重建单调队列$O(nm)$掌握了「变形出区间最值 → 套用三步法」这条主线再配合仓库中两份可运行的参考代码与配套测试数据docs/dp/code/opt/monotonic-queue-stack/、docs/dp/examples/opt/monotonic-queue-stack/就可以把这类优化自如地用于自己的题目中了。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考