单调队列/单调栈优化

介绍

前置知识：

单调队列、

单调栈。

设 表示在放第 个烟花时，你的位置在 所能获得的最大快乐值。

写出 状态转移方程：

这里的 是有范围的，。

我们尝试将状态转移方程进行变形：

由于 里出现了一个确定的常量 ，我们可以将它提到外面去。

如果确定了 和 的值，那么 的值也是确定的，也可以将这一部分提到外面去。

最后，式子变成了这个样子：

看到这一熟悉的形式，我们想到了什么？单调队列优化。由于最终式子中的 只和上一状态中连续的一段的最大值有关，所以我们在计算一个新的 的状态值时候只需将原来的 构造成一个单调队列，并维护单调队列，使得其能在均摊 的时间复杂度内计算出 的值，从而根据公式计算出 的值。

总的时间复杂度为 。

讲完了，让我们归纳一下单调队列优化动态规划问题的基本形态：当前状态的所有值可以从上一个状态的某个连续的段的值得到，要对这个连续的段进行 RMQ 操作，相邻状态的段的左右区间满足非降的关系。

单调队列优化多重背包

不了解背包 DP 的请先阅读

背包 DP。设 表示前 个物品装入承重为 的背包的最大价值，朴素的转移方程为

时间复杂度 。

考虑优化 的转移。为方便表述，设 ，则转移方程可以表示为：

设 。则方程可以表示为：

这样就转化为一个经典的单调队列优化形式了。 可以 计算，因此对于固定的 ，我们可以在 的时间内计算出 。因此求出所有 的复杂度为 。这样转移的总复杂度就降为 。

习题

• 「Luogu P1886」滑动窗口
• 「NOI2005」瑰丽华尔兹
• 「SCOI2010」股票交易