>原文链接<

  1. 什么样的方程可以斜率优化 ?
    • 形如 $F[i] = \min(\max){F[j] + g[i]+h[j]+s(i, j)}$ 的方程
    • 要求其中几项都有单调性
    • 如果没有那项同时与$i, j$有关的$s(i, j)$ 就可以用单调队列了
    • 当然,$s$可以是任何同时与$i、j$有关的函数(分别单调)
  2. 斜率优化的一般形式 :

  • 我们把上面的转移式子拆开来看。

    对于一条直线$y=kx+b$

    $y$就是我们转移的目标$F[i]$

    $b$是常量$F[j]+h[j]+g[i]$

    $k$是$s(i, j)$中有关$j$的那部分

    $x$就是$s(i,j)$中有关$i$的那部分

  1. 斜率优化维护的单调性 :

    考虑怎样的一条直线是再也用不到的。

  • 首先考虑队首的直线,它是我们准备拿出来更新当前状态的。

  • 之所以用它更新是最优方案,是因为它的$b$值比别的都小,在相同的$x$下,不管斜率是什么,当然$y$越小越好(也肯能是越大越好,视题意决定)。但由于斜率太大,它的增长速度比别的直线都快,一旦劣于后面的某条直线,以后就再也用不到了。所以将当前的$x$代入方程,比较队首直线和队首第二条直线得到的$y$值(也就是我们用对应$j$更新后的$F[i]$) 的大小关系,如果队首还是比后一个好,就直接算出$F[i]$。否则弹出队首,重复操作,直到队首优于第二个。然后更新$F[i]$,并准备将它入队。

  • 进而考虑队尾的直线。

  • 斜率小而截距大。引用学长CKH的一句话 :

  • 如果队尾直线和队尾的前一条直线的交点在它和将要入队的直线的交点的左侧,那么队尾直线必然没有意义了。 因为斜率是递减的,它已经被两条直线一块盖严实了!

    就按如上的规则更新队首队尾,每次用队首更新当前状态,再把当前状态压到队尾。

  • 维护队尾的细节 :

  • 我们设要加入的直线为 $i$,队尾直线为$r$,队尾的前一条直线为$r_1$。

  • 那么若要弹出队尾,相当于$x_{ir}\ge x_{rr_1}$

  • $k_{r1}x+b_{r1}=k_rx+b_r$

  • $x_{ir} = \frac{b_r-b_i}{k_i-k_r}$ $x_{ir_1}=\frac{b_r-b_{r_1}}{k_{r_1}-k_r}$

  • 也就是$\frac{b_r-b_i}{k_i-k_r}\geq \frac{b_r-b_{r_1}}{k_{r_1}-k_r}$

  • 我们交叉相乘,就避免了除法带来的常数和精度误差。(注意维护的凸包是怎样的,然后处理符号)

  1. 斜率优化练习题: