斜率优化动态规划

• $斜率优化的作用$斜率优化的作用

$F_i=\min (F_j+s_i^2+(s_j+L{)}^2-2s_i(s_j+L))$Fi​=min( Fj​+si2​+(sj​+L)2−2si​(sj​+L) )

形如这个式子 关于i的项 与 关于j的项 混杂(相乘) 的状态转移方程, 可以使用斜率优化来加速 .

接下来以优化这个式子为例说说斜率优化.

• $斜率优化的内容$斜率优化的内容

将上方给出的式子去掉 $min$min, 仅关于 $j$j的项放在左边, 关于 $i$i的项放在右边得 $\downarrow$↓

$F_j+(s_j+L{)}^2=2s_i{s}_j+F_i-s_i^2+2L{s}_i$Fj​+(sj​+L)2=2si​sj​+Fi​−si2​+2Lsi​

这个时候原式为 $y=kx+b$y=kx+b 的形式, 其中

• $y=F_j+(s_j+L{)}^2$y=Fj​+(sj​+L)2
• $k=2s_i$k=2si​
• $x=s_j$x=sj​
• $b=F_i-s_i^2+2L{s}_i$b=Fi​−si2​+2Lsi​

$\because j\in [1,i)$∵j∈[1,i) 且为一个单调递增的正整数数列
$\therefore x,y$∴x,y都随 $j$j 单调递增.
又 $\because k$∵k 始终不变
$\therefore$∴ 上式代表了一个 斜率不变, 随着经过点 $(x,y)$(x,y)的变化, 截距也随之变化的直线 .

暂且称 $(x,y)$(x,y) 代表的点为 决策点,

由于单调递增, 决策点 构成的图象为 下凸壳 , 这里给出概念图.

备注: $k_{bc}\&lt;k_{cd}$kbc​<kcd​ .

我们需要 截距 $b$b 最小进而使答案最优, 即找到一个最优的 决策点 .

$找到第一条斜率大于k的线段,过左端点的直线截距即为最小值.$找到第一条斜率大于k的线段,过左端点的直线截距即为最小值.

• $斜率优化的实现$斜率优化的实现

使用 单调队列 维护, 没学过的可以看 这里 了解一下,
具体地说:
对上转移方程, 应当维护斜率从队首到队尾的单调递增队列,

设当前是第 $i$i 个点,

1. 不断弹出队首, 直到 队首 与 次队首 的斜率大于等于 $k$k 或 队列长度为 $1$1 , 队首即为当前最优的 决策点 .
2. 不断弹出队尾, 直到 队尾 与 次队尾 的斜率小于 次队尾 与 $i$i 的斜率, 将第 $i$i 个点从队尾入队(对后面来说新的决策) .

时间复杂度 $O\left(N\right)$O(N) .

经典例题

• $斜率优化的变形$斜率优化的变形

1. $k$k不确定正负, 此时不能弹出队首, 但是仍然可以维护单调性, 二分查找来弥补, 时间复杂度 $O\left(NlogN\right)$O(NlogN) , 例题 , 下有数学解释 .
2. 决策点的横坐标不单调递增, 需要在任意位置插入决策点, $待填坑$待填坑 .

• $相关数学推导补充$相关数学推导补充

以 该题 的式子为例, (已经去掉 $\min$min),

$F\left[i\right]=F\left[j\right]+s_t\left[i\right]\ast \left(s_c\right[i]-s_c[j\left]\right)+S\ast \left(s_c\right[N]-s_c[j\left]\right)$F[i]=F[j]+st​[i]∗(sc​[i]−sc​[j])+S∗(sc​[N]−sc​[j])

设 决策 $j$j 比 决策 $k$k 优, 则
$F\left[j\right]+s_t\left[i\right]\ast \left(s_c\right[i]-s_c[j\left]\right)+S\ast \left(s_c\right[N]-s_c[j\left]\right)\&lt;F\left[k\right]+s_t\left[i\right]\ast \left(s_c\right[i]-s_c[k\left]\right)+S\ast \left(s_c\right[N]-s_c[k\left]\right)$F[j]+st​[i]∗(sc​[i]−sc​[j])+S∗(sc​[N]−sc​[j])<F[k]+st​[i]∗(sc​[i]−sc​[k])+S∗(sc​[N]−sc​[k])
化简得
$\frac{F\left[j\right]-F\left[k\right]}{s_c\left[j\right]-s_c\left[k\right]}\&lt;S+s_t\left[i\right]$sc​[j]−sc​[k]F[j]−F[k]​<S+st​[i] .
若 $s_t\left[i\right]$st​[i] 单调递增, 则 $j$j 在以后不可能比 $k$k 更优了, 所以可以执行弹出队首的操作 .
否则 $j$j 可能在以后的某一个决策中比 $k$k 更优, 不能直接弹出队首 .