在我们回忆一下最基础的斜率优化模板题的过程:
- 将初始状态入队。
- 每次使用一条和相关的直线去切维护的凸包,找到最优决策,更新。
- 加入状态。如果一个状态(即凸包上的一个点)在加入后不再是凸包上的点,需要在加入前将其剔除。
二分/CDQ配合斜率优化分别是对步骤2和步骤3的实现进行一些修改以适应一些特殊情况。
二分+斜率优化
众所周知,当我们在这个点寻找最优决策时,会使用一个和相关的直线去切我们维护的凸包。切到的点即为最优决策。对于一个下凸包(上凸包同理),且的斜率随着单调递增,如果队首的两个点斜率小于时,我们就可以把第一个点出队,因为第一个点以后都不可能成为最优决策了。这就是斜率优化模板题的思路。因为每个点只会被出队一次,所以复杂度是的。
但是对于有些问题,并不是递增的。所以我们需要保存凸包的每一个节点,然后每次用当前的直线去切这个凸包。这个过程显然可以使用二分解决,因为凸包上相邻两个点的斜率是有单调性的。
例题: Codeforces 1420E
CDQ/Splay+斜率优化
我们知道,在步骤3结束时,我们会向凸包中加入这个状态。在模板题中,这一点很好实现,因为状态点的横坐标是单调的,我们只需要把这个点插入到队尾即可。但是如果没有单调性,该如何实现?我们可以使用平衡树,实现凸包的动态维护,但是这样比较麻烦,我们考虑另外一种方法:CDQ分治。
斜率优化是为了快速寻找动态规划的最优决策点。如果我们使用状态集合中的每个状态去更新。只要最优决策点满足,那么我们的决策就一定是最优的。
我们可以使用CDQ分治,CDQ(l,r)
代表求。对于CDQ(1,n)
,我们先调用函数CDQ(1,mid)
解决。然后我们对这个区间内的点建一个凸包,然后使用这个凸包去更新。
对于中的每个点,如果它的最优决策的位置是在这个区间,在这一步操作中他就会被更新成最优答案。当执行完这一步操作时,我们发现中的所有点已经发挥了全部的作用,凸包中他们存不存在已经不影响之后的答案更新。因此我们可以直接舍弃这个凸包,并使用CDQ(mid+1,n)
解决右区间的问题。复杂度