单调队列优化DP

        在之前的日志中提到了单调队列的一个用途——求固定长区间最值。这里介绍单调队列的另一种用途——优化DP。

        在状态转移方程中，有一种方程十分常见，它的形式如下所示：

$$dp(i)=\min/\max\{s(k)\}+c(i),l(i)\leq k \leq r(i)$$

        这里dp由s转移而来（s可以就是dp本身），s的取值范围由l(i)和r(i)确定，c(i)为转移代价，与k的选取无关。在求解这个方程时，需要for一遍i，还要for一遍k才可以得到dp值。如果l和r的距离很大，时间复杂度将达到O(n²)，转移时间消耗不可忽视。
        当从小到大递推dp值时，如果发现l和r均单调递增，这时可以用单调队列优化DP过程，降低时间复杂度。这里的单调队列仍然存下标，具体算法如下：

1. 定义开始点key，key初始化为最小的l值，如果从0开始计数则key=l(0)。
2. 对于枚举到的每一个i，将[key，r(i)]的下标加入单调队列，并更新key=r(i)+1。
3. 取队首元素。如果队首元素不在[l(i)，r(i)]中，忽略该元素继续取队首。最终得到的队首元素所指的元素即为最值。

算法正确性证明：
        下证i=k+1时可以求出最值：
        倘若l(k+1)>r(k)，那么由于key更新为r(k)+1≤l(k+1)，易知[l(k+1)，r(k+1)]中的所有元素都在i=k+1时入队，显然可以得到最优解。
        倘若l(k)≤l(k+1)≤r(k)，如果i=k+1的最优解出现在[r(k)+1,r(k+1)]中，那么这一个区间的值一定在i=k+1时入队，一样可以求出最优解。如果i=k+1的最优解出现在[l(k+1)，r(k)]中（假设为p），现证明p这个元素不可能被“剔除”。倘若存在q由于比p更优将p剔除出队列，那么一定有q>p，容易知q也在[l(k+1)，r(k)]中，那么q应该是i=k+1时比p更优的解，这与p最优矛盾。因此p最优时不可能被剔除，最终仍可以得到最优解。
        综上所述，算法正确。
        单调队列求固定长区间最值其实是这种方法的特殊情况。