关于斜率优化的DP

以前写单调DP都是浑浑噩噩的，最近又重新回去看ZZX去年写的东西，还有汤泽，杨哲的论文

总算把斜率优化弄懂了……

对于这样的一类DP方程

f[i]=min{a[i]*x[j]+b[j]}

a[i]是和i有关的函数，x[j],b[j]是和j有关的函数或常数

求解这个问题朴素是O(n^2)的，我们可以将它优化到O(n)或O(nlogn)

我们可以把它改写成这个样子

-a[i]*x[j]+f[i]=b[j]

把-a[i]看做斜率，f[i]看做截距，每一个决策相当于平面上一个点

最优决策显然在平面点集的凸包上

要求f[i]的最小值，就相当于将一条斜率为-a[i]的直线不断向上平移，碰到的第一个点就是截距最小的点

也就是f[i]的最优决策

如果横坐标和斜率均单调，我们就可以维护一个单调队列，队首指针不断往后走，每个点只会访问一次，复杂度为O(n)

如果均不单调，有时我们可以排序使得其中一个单调，否则无法用斜率优化的DP做

横坐标单调：

二分凸包上的点，找到这样一个点x，使得

x和x左边的点的所在的直线斜率小于当前直线斜率

x和x左边的点的所在的直线斜率大于当前直线斜率

将直线插入，维护凸壳

斜率单调：

关于横坐标建立一棵Splay

然后在Splay中维护凸壳

以上说的是取min，那么维护的是下凸壳

取max的话是维护上凸壳

如果方程是

f[i]=min{a[i]*x[j]+b[i]*y[j]}

的话，可以将其变为

f[i]=min(a[i]/b[i]*x[j]+y[j])*b[i]