【摘要】单调队列优化 DP 0. 定位 单调队列优化 DP，解决的是这样一类问题： 状态转移的「决策集合」是一个随主状态单调滑动的窗口，且决策的优劣可以提前与主状态 i 解耦。满足这两点时，原本 O(nm) 的枚举被改为 O(n)。 1. 朴素形态与优化动机 几乎所有这类 DP 都长这样： dp[i] = 阅读全文