单调性问题总结.docx

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)求出区间最值。

能用单调队列解决的问题有一个特性：两个元素哪个比较优是可以只用它们本身就可以判断的，如果判断哪个比较优与当前状态有关，那么如果随着状态改变两个元素的优劣颠倒了， 单调队列就失去了作用。

斜率优化：
斜率优化解决的问题是：在只用两个元素本身信息的情况下，如何比较这两个元素的优劣。
关键问题：分离参数。

步骤如下：
写出转移方程，形式如：
其中f是最优结果，g(i)和h(i)是只与i有关的函数，x(j)、t(j)是只与j有关的函数。（如果还有常数基本上都可以归纳进某个函数里。）

我们试着比较两个决策j1和j2的优劣，假设j1<j2，f越小越优，则只有

成立的时候，j2会优于j1。
不等式可以化简如下：

这个不等式中还是有i的存在，也就是j1和j2的优劣与i有关，还需要变形。

（现在要用除法了，假设x(j2)-x(j1)是正数。）
为了简便，设
得到最后的不等式：
现在所有与j有关的都在左边，与i有关的都在右边。

现在发现：左边的式子和斜率的式子很像，如果(x(j),y(j))是第j个点的话。

这时我们试着分析一个点有没有保留的必要。
因为斜率只存在在两个点之间，我们可以画3个点。
J2
J3

J1

第一种情况，前两个点的斜率大于后面的两个点。
如果j1j2的斜率大于g(i)，那么j2优于j1，因为j2j3的斜率更加小，所以j3不一定优于j2，所以j2有可能成为最优。
J3
J2

J1

第二种情况，前两个点的斜率小于后面两个点。
当j1j2的斜率大于g(i)时，因为j2j3的斜率更大，也一定大于g(i)，所以j3永远比j2优，j2就没有必要保留了。

通过两种情况的分析，发现：决策的斜率一定是单调递减的。（这个情况下。）

DP的方向性决定了区间的方向是固定的。
所以我们可以用单调队列来保存决策。

接下来是最优决策在哪里的问题。
如果g(i)单调递减，那么一旦队首的元素不是最优了，就永远不可能是最优的，可以删掉，直到队首元素最优为止。所以最优决策在队首。
如果g(i)单调递增，我们可以把不等式中j1和j2反过来写，这样最优元素在队尾。
如果g(i)不单调，那么最优决策可能在任意一个位置，但是因为有序，所以可以用二分查找，找到g(i)夹在两个斜率之间的位置。

还有一个问题要注意的：
如果x(j)不单调怎么办？
x(j)不单调，那么新的元素有可能在中间，就不可以用单调队列了。
动态维护有序的数据结构是平衡树，可以编一棵平衡树来解决这个问题。
用Splay比较好，因为要成段删除。（或者非旋转式Treap。）
相当于维护动态凸包，每次插入一个点，把这个点左右不符合单调性的都删除。

三分法和黄金比例三分法：
三分法其实不一定与DP有关，它的用途是：求单峰模型的极值。
什么叫单峰模型呢？意思是：只有一个极点，极点左边和右边都是单调的。（明显单调性相反。）

明显二分法不适合这个模型的极值。
三分法做法如下：

一开始取一个一定包括了最大值的区间[L,R]。
算出两个3分点A和B。

然后比较点A和点B，假设点A比较优
那么区间[B,R]就没有必要保留了，
接下来三分的区间就是[L,B)了。
（如果B比较优，那么下一个区间是(A,R]）

T(n)=T(2n/3)+2O(k)
（O(k)是求一个值的时间。）
每次去掉了1/3的区间，所以时间复杂度是O(2klogn)的。
每次要求两个值A和B，如果求值的时间比较大，可能会有问题。

观察上一个图，发现如果每次求的不是刚好三分点而是特定比例的点的话，A点和C点其实是可以重合的。
即LA:LB=LA:LR，很明显这是黄金比例。
也就是每次不取1/3和2/3的点，每次取0.382和0.618的点，那么删掉多余区间之后，下一次取的点有一个肯定和原来取的有一个重合，这样就只用求一个值了。
所以黄金比例三分法比直接三分要优。
T(n)=T（0.618n)+O(k)
时间复杂度是O(klogn)的。

线性规划：
（线性规划最后还是和斜率优化差不多，感觉没有斜率优化简洁。）
如果我们可以把转移方程写成：

这样的形式，其中A、B函数只和i有关,x、y函数只和j有关，那么我们可以把(x(j),y(j))看成一个点。
我们过这个点作一条斜率为的直线。
把直线方程解出来得到：
截距（与y轴的交点的纵坐标）为
刚好是答案的1/B(i)。
因为对于同一个i，所有直线的斜率都一样，B(i)也一样，所以对于i的最优决策就是截距最大的直线。

（设A、B都大于0，则斜线斜率小于0，否则相反）
明显，如果两个点x(1)<x(2),y(1)<y(2)，那么第一个点是没有必要保存的。

那么按照x排序之后，y一定单调递减。

接下来还可以证明，相邻决策的斜率是单调递减的。
如果存在连续两个递增的话，夹在中间的点无论什么情况截距都不会最大。

接下来是怎么求最大截距是那一条的问题：

实际上，因为点的分布，截距会呈现一个单峰的形式，用三分法就可以求出。
（证明可以用数学，也可以直观地想：保留的点一定是呈现一个1/4圆的样子，在上面作同一斜率的斜线，越靠近切线的截距越大，所有肯定是单峰的。）