斜率优化 学习笔记

发表于
为什么不用李超树呢？

适用范围

斜率优化适用于转移方程中有 $i,j$ 相关的相乘的量出现。

原理

决策单调性，可参考单调队列优化。

操作方法

  1. 正确地写出状态转移方程式。

  2. 令当前状态为 $i$，则“任取 $i>j>k>0$ 中的 $j$ 和 $k$”，分别写出转移方程式。

  3. 将二者相减，得到通过 $j$ 转移比通过 $i$ 转移更优所需满足的不等式组。

  4. 将 $i$ 有关的视作主元，分开一次项与常数项。

  5. 得到斜率。

  6. 根据斜率单调性维护单调队列（同普通单调队列优化）

以此题为例：

  1. $$f_i=min,{,f_j+w_{j+1}×l_i,}(0≤j<i)$$

  2. $$f_i=min,{,f_j+w_{j+1}×l_i,}(0≤j<i)$$

$$f_i=min,{,f_k+w_{k+1}×l_i,}(0≤k<j)$$

3~5.
$$ f_j-f_k\le (w_{k+1}-w_{j+1})×l_i$$
$$\text{即斜率为} \frac{f_j-f_k}{w_{k+1}-w_{j+1}}$$

  1. 1
    2
    3
    4
    5
    6
    for(int i=1;i<=n;++i) {
    		while(l<r&&slope(q[l],q[l+1])<=a[i].y) ++l;
    		f[i]=f[q[l]]+a[q[l]+1].x*a[i].y;
    		while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
    		q[++r]=i;
    	}