动态规划的简单优化 单调队列

· · 个人记录

单调队列适合这样的转移方程：

f(i) = \min\limits_{L_i \le j \le R_i} \{f(j) + a_j\} + b_i \space \text{s.t.} \space L_t \lt L_{t + 1}, R_t \lt R_{t + 1}

如果我们使用朴素的方法求解这个方程，时间复杂度大约是 O(n^2) 的（实际上是 O(\delta n)，其中 \delta 是每一个区间的宽度）。这是因为对每一个点 i，我们都需要遍历一个区间内的 j 并且取其最值。

我们发现，对不同的 i，我们计算的 j 是有重叠的；并且，由于这些计算出的结果并不依赖 i，因此我们可以使用单调队列的方法，保存重叠的 j 区间中 f(j) + a_j 的最大值。

这样，在计算 f(i) 的时候，我们只需要在单调队列中加入找到在这个区间内的最大值即可。由于这些区间都是递增的，因此超出了某个点 i 的点 j，我们可以直接将其从队列中删除。

这样实际复杂度达到 O(n)