关于斜率优化这个玄学东西一些自己的bb理解(似乎和网上的理解方法都不太一样?)

基本形式

dp[i]=minj<i{a[i]b[j]+c[i]+d[j]} dp[i] = \min_{j < i}\{a[i] * b[j] + c[i] + d[j]\}

其中bb具有单调性(假设bb单增)

假设我们有两个决策j,k(k<j)j,k(k < j),且对于ii而言,在jj的决策比kk优,那么有

a[i]b[j]+c[i]+d[j]<a[i]b[k]+c[i]+d[k]a[i](b[j]b[k])<d[k]d[j]d[k]d[j]b[j]b[k]>a[i]d[j]d[k]b[j]b[k]<a[i] \begin{aligned} &a[i] * b[j] + c[i] + d[j] < a[i]*b[k] + c[i] + d[k]\\\\ \Rightarrow &a[i](b[j] - b[k]) < d[k] - d[j]\\\\ \Rightarrow &\frac{d[k] - d[j]}{b[j] - b[k]} > a[i]\\\\ \Rightarrow &\frac{d[j] - d[k]}{b[j] - b[k]} < -a[i] \end{aligned}

不难发现,如果 满足这个条件的话,那么 的决策比

Slope(j,k)=d[j]d[k]b[j]b[k]Slope(j, k) = \frac{d[j] - d[k]}{b[j] - b[k]},把bb看作横坐标,dd看作纵坐标。

因为当前的a[i]-a[i]是固定的,所以对于某一个决策kk而言,如果某个在它后面的决策jj比它优,在图像上来看就是jj点在斜率为-a[i],且过k点的直线(也就是下图中的红色直线)的下方

19-1-17-1

继续观察发现,对于像j2j_2这种不在下凸壳上的点,无论a[i]-a[i]为多少,它一定不会是最优决策

证明:

  1. j2j_2决策比kk劣那显然j2j_2不是最优
  2. j2j_2决策比kk优(即上图所示情况),则j3j_3的决策一定比j2j_2优,因此j2j_2肯定不为最优

因此,最优解一定出现在下凸壳上,我们可以用单调栈维护凸壳

但是,下凸壳上的哪个点才是最优的呢?

不难发现,最优解xx一定满足Slope(x1,x)<a[i]Slope(x - 1, x) < -a[i]Slope(x+1,x)>a[i]Slope(x + 1, x) > -a[i]

也就是说,a[i]-a[i]刚好夹在它与前后两个点的斜率之间

通过图像感性理解,其实就是把一条斜率为a[i]-a[i]的直线从无穷小处移过来,于凸壳第一个相交的点

因为这个点往左/右走的话,斜率一定会分别变小/变大,而这两种情况都会使得答案更劣,于是这个交点就是最优解

特别地,如果a[i]-a[i]单调递增,可以直接用单调队列维护,直接把队首小于a[i]-a[i]的不断弹出即可

否则就必须在单调栈上二分查找

乱bb一些东西

自己理解来看,斜率优化在优化dp转移时,主要是两个部分。首先根据斜率的一些性质建立出凸壳,去掉了很多不需要的转移,并且使得有用的转移是斜率单调的。然后对于每次转移,就只需要在凸壳上二分斜率,或是直接维护单调队列,用指针扫一下即可。

这段东西都是自己瞎bb的,要是理解错了就gg了。。。

更一般的情况

上面的式子中,如果b[i]b[i]也不单调的话,就需要用Splay维护动态凸包/CDQ分治优化解决了

一般来说直接写分治会更加简便灵活,这个东西也类似于一个三维偏序,一维下标要满足j<ij<i;一维b[]b[]要满足在静态的时候单增;还有一维是斜率a[i]-a[i]

与分治有关的部分在这里也提到过,这里就重点写下计算贡献的过程

考虑用[l,mid][l,mid]中求出的dp值去更新[mid+1,r][mid+1,r]的dp值:

由于这个子问题已经是静态的了,顺序对此时的贡献是没有影响的,于是可以直接排序

对于[l,mid][l,mid]中的所有决策点按b[]b[]排序,可以线性构造出这个凸壳

再对[mid+1,r][mid+1,r]中的状态按斜率排序,这样又能线性在凸壳中找到最优点

总复杂度O(nlog2n)O(n\log^2 n),写归并排序的话是O(nlogn)O(n\log n)