斜率优化dp复习

发表于 2019-07-15 分类于算法小结

发现自己几乎忘记斜率优化怎么写了，就来复习了一下。

对于一个$dp_i=\max_{j\lt i} \{dp_j+f(i,j)\}$的方程，如果$f(i,j)=a_i+b_j$，则$dp_{i}=a_i+\max_{j<i}{dp_j+b_j}$可以直接做。

如果$f(i,j)=a_i+b_j+c_id_j$呢？$d_j$互不相同

$dp_i=a_i+\max_{j\lt i}\{dp_j+b_j+c_id_j\}$

这个$b_j+c_id_j$取$\max$，相当于，对于$f_j(x)=b_j+dp_j+d_jx$，在$c_i $位置求最大值。

考虑只有三条直线$y_1=k_1x+b_1,y_2=k_2x+b_2,y_3=k_3x+b_3(k_1>k_2>k_3)$

如果$ $，则如果$y2y_1,y_2y_3$至少一个成立。且$x $这一段区间最大值不能轻易得出。此时就可以直接把直线2删掉。

这样把每条直线按照$k$值排序，相邻两个$\frac{b_2-b_1}{k_1-k_2}$一定是升序的，这样每个位置的max可以方便确定。

对于$c_i $单调的情况，设$c_i $升序，否则可以$c_i=-c_i,d_i=-d_i$

考虑两条直线$y_1=k_1x+b_1,y_2=k_2x+b_2(k_1>k_2)$，

若$y_1\ge y_2$，则$x\ge \frac{b_2-b_1}{k_1-k_2}$，$y_1\le y_2$自然就是$x\le \frac{b_2-b_1}{k_1-k_2}$。

此时直线2显然不可能是答案了，可以直接删掉

当然，如果$c_i$不是单调的，没关系，可以二分一下。

如果$d_i$是单调的，可以直接从一边插入，并且删除一些直线。

如果$c_i$不是单调的，每次插入的时候二分到该插入的位置，先判断是否可以加入，如果可以加入则加入，且对左右两边的直线分别删除，可以用平衡树类似物解决。