DP 单调性问题总结罗梓璋单调性：单调性，意思是保持同样的趋向，单调递增或者单调递减。在 DP 中，很多情况下，原来是没有单调性的，但是删去不可能的决策之后，剩下的决策会呈现单调性。具有单调性的决策是有序的，最优决策可能直接在头或者尾 O(1)得到，也可以二分查找 O(logn)得到，总体比 O(n)寻找最有决策的时间要少很多。所以单调性可以解决的问题是：保留可能决策，快速寻找最优决策。单调队列：单调队列的本质是双端队列，单调队列的内部是单调的，新元素从队尾加入，假如新元素加入后不满足单调性，那么令原来队尾的元素出队，直到新元素加入后满足单调性或者队列空了。如单调递减队列原来是 5 2 1，加入一个元素 3，则队列为：5 3。单调队列的开头元素在不满足条件时出队。（另外一种加入元素的可能是，二分查找合适的位置，代替原来的元素，但是不能直接插入元素，在某些题目可能有。例如上面的例子为:5 3 1 或 3 2 1，视具体情况。）单调队列是最简单的处理单调性问题的数据结构，最大的用处是：维护区间最值。维护区间最值的要求是，区间的移动方向固定。（要保证队首不加入元素。）既然区间移动方向固定，那么可以区间每移动一个单位，那么多了一个新的元素，少了一个旧的元素。新的元素一定在最后，旧的元素一定在最前。假如队首的元素已经离开了区间，那么让它出队。我们考虑两个元素 A 和 B，B 比 A 优，而且 B 在 A 的后面，因为 A 比 B 先离开区间，所以有 B 在 A 永远也不可能是最值了。所以新的元素加入队列后，假如队列队尾的元素不如新的元素优，那么就可以删除掉队尾原来的元素，直到队尾的元素比新元素优，才把新的元素加入队尾。我们发现这样的队列和单调队列完全符合，队列中前一个元素一定比后一个优，满足单调性，而且模型也一样。这样区间最值一定是队首的元素，可以 O(1)求出区间最值。能用单调队列解决的问题有一个特性：两个元素哪个比较优是可以只用它们本身就可以推断的，假如推断哪个比较优与当前状态有关，那么假如随着状态改变两个元素的优劣颠倒了， 单调队列就失去了作用。斜率优化：斜率优化解决的问题是：在只用两个元素本身信息的情况下，如何比较这两个元素的优劣。关键问题：分离参数。步骤如下：写出转移方程，形式如：J1J1J2J3J2其中 f 是最优结果，g(i)和 h(i)是只与 i 有关的函数，x(j)、t(j)是只与 j 有关的函数。（假如还有常数基本上都可以归纳...
