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

引入

对于一个$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)$

如果$\frac{b_2-b_1}{k_1-k_2}\le \frac{b_3-b_2}{k_2-k_3} $,则如果$y2\lt y_1,y_2\lt y_3$至少一个成立。且$\frac{b_2-b_1}{k_1-k_2}\le x\le \frac{b_3-b_2}{k_2-k_3} $这一段区间最大值不能轻易得出。此时就可以直接把直线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$不是单调的,每次插入的时候二分到该插入的位置,先判断是否可以加入,如果可以加入则加入,且对左右两边的直线分别删除,可以用平衡树类似物解决。

标签: DP

添加新评论