单调性问题总结.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的优劣，假设j1j2，f越小越优，则只有成立的时候，j2会优于j1。不等式可以化简如下：这个不等式中还是有i的存在，也就是j1和j2的优劣与i有关，还需要变形。（现在要用除法了，假设x(j2)-x(j1)是正数。）为了简便，设得到最后的不等式：现在所有与j有关的都在左边，与i有关的都在右边。现在发现：左边的式子和斜率的式子很像，如果(x(j),y(j)是第j个点的话。这时我们试着分析一个点有没有保留的必要。因为斜率只存在在两个点之间，我们可以画3个点。J2J3J1 第一种情况，前两个点的斜率大于后面的两个点。如果j1j2的斜率大于g(i)，那么j2优于j1，因为j2j3的斜率更加小，所以j3不一定优于j2，所以j2有可能成为最优。J3J2J1第二种情况，前两个点的斜率小于后面两个点。当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圆的样子，在上面作同一斜率的斜线，越靠近切线的截距越大，所有肯定是单峰的。）