简介
斜率优化是一种利用数形结合优化dp的方式, 属于一种决策单调.
斜率优化可以把某些 (1D/1D) 动态规划的复杂度优化到 (O(n)) 或 (O(nlogn)).
形式
当动态规划的转移方程形如
其中 (a[i]) , (d[i]) 仅与 (i) 有关, (b[j]) , (c[j]) 仅与 (j) 有关.
当(a[i])和(b[j])均单调时, 可以优化为(O(n)); 否则, 文末会介绍一些优化.
设 (min / max(a[i] * b[j] + c[j]) = b), (a[i] = k), (b[j] = x_j), (c[j] = y_j), 可以发现
即
这显然是一条过 ((x_j,y_j)) , 斜率为 (k), 截距为 (b) 的直线.
而我们的任务就是选取合适的 (j) , 使直线的截距 (b) 最大/小.
下面以取最小值为例.
即一条直线kx+y，斜率一定，要求最小截距。也就是将(b[j],G[j])看做j对应的点，一条斜率为a[i]的直线从负无穷向上平移，第一个碰到的点。
这个点一定在i对应点集的凸包上，而且我们是取最小值，所以一定是在下凸壳上，而且是这条直线与这个凸壳的切点。我们要维护这样一个凸壳，这可以用单调队列实现。
先考虑如何取出最优决策.
设que是一个横坐标递增的具有下凸性的点集，取出队头的两个点，如果这两点的连线斜率＜a[i]
显然直线不与凸壳相切，又因为斜率是单调（假设是增加）的，所以后面的直线肯定也不会切于这点，这时直接把队头弹出即可。一直这样维护直到队头两点斜率>=a[i]，取出队头转移状态即可。
再考虑将点i插入凸壳中，设t1，t2为队尾的两个点，k（i，j）为i，j两点连线斜率，下凸壳的斜率显然是增加的，那么如果出现k(i，t1)<k（t1，t2）时，t1就没有存在的必要了，将它删除即可。
一直这样维护直到出现k(i，t1)>k（t1，t2），就保证了这个队列保存的点集的下凸性。
有时候斜率和横坐标不是全单调的:
- 斜率不单调：
二分凸包上的点，找到这样一个点x，使得
x和x左边的点的所在的直线斜率小于当前直线斜率
x和x左边的点的所在的直线斜率大于当前直线斜率
将直线插入，维护凸壳 - 横坐标不单调：
用set维护凸壳