斜率优化 学习笔记

模板及讲解

斜率优化解决什么问题

DP方程形如$dp(i)=\min(dp(j)+(a_i-a_j)^2)$,有像$(a_i-a_j)^2$这样与$i, j$都相关的信息,就不能用单调队列等来优化,要利用斜率优化来做。

斜率优化

例题:Bzoj 1010

有$n$个数${C_n}$,分成连续的若干段,每段(假设从第$j$个到第$i$个组成一段)的分数为$(X-L)^2$,$X$为$j-i+ \sum C_k , i \leq k \leq j$,其中$L$是一个常量。目标:各段分数的总和最小。

设$dp(i)$表示分组完前$i$件物品的最小花费, $sum_i$表示是前$i$件物品的长度和。
$dp(i)=\min(dp(j)+(sum_i-sum_j+i-j-L-1)^2|1 \leq j < i)$
设$S_i=sum_i+i$,则$dp(i)=\min(dp(j)+(S_i-S_j-L-1)^2)$
设$P=L+1​$, 代入,$dp(i)=dp(j)+(S_i-S_j-P)^2$

证明决策单调性

使用数学归纳法证明。
假设$i$前有两个决策$j, k(j < k)$, 且决策$k$比$j$优,则
$$dp(j)+(S_i-S_j-P)^2 > dp(k)+(S_i-S_k-P)^2 –(1)$$
假设$i$后面的某状态$t$有$S(t)=S(i)+v$,则
$$dp(j)+(S_t-S_j-P)^2 > dp(k)+(S_t-S_k-P)^2$$
$$dp(j)+(S_i-S_j-P)^2 +2v(S_i-S_j-P) + v^2 > dp(k)+(S_i-S_k-P)^2 +2v(S_i-S_k-P) + v^2$$
因为$S_i-S_j > S_i-S_k$并且$P \in \mathbb N+$,所以$S_i-S_j-P > S_i-S_k-P$,综合(1),假设(1)成立

斜率斜截式

将常数、仅和$i$相关的项、仅与$j$相关的项、$i、j$乘积项分开

分解,$dp(i)=dp(j)+S_i^2-2S_i \cdot (S_j + P) + (S_j+P)^2$
移项,$2S_i \cdot (S_j+P)+dp(i)=dp(j)+S_i^2+(S_j+P)^2$
$dp(j)+(S_j+P)^2+S_i^2=dp(i)+2S_i(S_j+P)$
把左边($dp(j)+(S_j+P)^2+S_i^2$)看成平面直角坐标系的$y$坐标,右边的$2(S_j+P)$看成$x$坐标。
那么这就是一条$k=S_i, b=dp(i)$的直线方程。决策$j$可以表示为坐标$(2(S_j+P), dp(j)+S_i^2+(S_j+P)^2)$
这里每一条直线的$x$都单调递增,$k$也单调递增。且对于同一个$i$,$k$为定值,所以我们对于每个$i$转移时只需要在知道斜率的情况下将截距$b=dp(i)$最小化。

决策的舍弃 (l)

那么现在问题转化为斜率为$S_i$的直线过一个决策$j$($j$点),求出截距最小的那一条直线。
那么如果过了$j$点就代表从$j$状态转移到$i$。现在有以下情况:

Markdown

$k_{AB}$的斜率比直线斜率$S_i$小,那么就要舍弃$A$点。后面点更优,因为

直线过$A$点时
Markdown
直线过$B$点时
Markdown
比较
Markdown
显然在$B$点截距$dp(i)$更小,比$A$点更优,并且直线斜率单增,以后所有的斜率都不会从$j$转移。

因为符合决策单调性,$k$递增,所以用单调队列维护点,实际上是维护了一个凸壳。如果在单调队列中,$k_{q_{l}q_{l+1}} < S_i$,那么就要舍弃$l$.

对于一条斜率为$k$的直线,将他放到凸壳中的应该排的位置即为最优决策点。由于$S_i$单增,所以凸壳左端点必为最优决策。

决策的舍弃 (r)

当前的$i$转移完后,要将其加入单调队列以便$i+1$选择决策。要维护下凸包,就必须让单调队列里的$k$单调递增。
Markdown
如图,新增点与$C$连线可以满足下凸包性质(选这个点比$D,E$截距更小,答案更优),所以$D,E$两点要舍弃
如果在单调队列中,$k_{q_rq_{r-1}} > k_{q_rq_{i}}$,那么就要舍弃$r$.

因为$x$坐标单增,所以新决策一定在凸壳右边。

代码

例题:Bzoj 1010

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, P, dp[50005], s[50005];
LL l, r, que[150005];
inline db getK(int k, int j) {return (db)(dp[k] - dp[j] + (s[k] + P) * (s[k] + P) - (s[j] + P) * (s[j] + P)) / (2.0 * (db)(s[k] - s[j]));}
//计算两个点之间斜率
void clean() {}
int solve() {
clean();
scanf("%lld%lld", &n, &P), s[0] = 0, P++;
for (int i = 1; i <= n; i++) scanf("%lld", &s[i]), s[i] += s[i - 1];
for (int i = 1; i <= n; i++) s[i] += i;
dp[1] = 0, l = 1, r = 1; //原点是决策点 r必须为1
for (int i = 1; i <= n; i++) {
while (l < r && getK(que[l], que[l + 1]) <= (db)s[i]) l++;
//l必须严格小于r,因为单调队列中要有两个元素
dp[i] = dp[que[l]] + (s[i] - s[que[l]] - P) * (s[i] - s[que[l]] - P);
while (l < r && getK(que[r - 1], que[r]) >= getK(que[r], i)) r--;
que[++r] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
int main() {
solve();
return 0;
}

易错点:
1、que[l]l区别
2、原点是决策点 初始化r必须为1
3、单调队列中要有两个元素才能算斜率,所以l < r
4、斜率优化实数会被卡精度,用叉积来判

数的方法求斜率

我们设$i$前有两个决策$j, k(j < k)$, 且决策$k$比$j$优,则
$$dp(j)-2S_i(S_j+P)+(S_j+P)^2 > dp(k)-2S_i(S_k+P)+(S_k+P)^2$$
将包含$i$的移到左边,其他移到右边
$$-2S_i(S_j+P)+2S_i(S_k+P) > dp(k)-dp(j)-(S_j+P)^2+(S_k+P)^2$$
把左边$S_i$提取出来,再把提取出来的式子除到右边($S_i-S_j > 0$)
$$S_i > \frac{dp(k)+(S_k+P)^2-dp(j)+(S_j+P)^2}{2(S_k-S_j)}​$$
令$k_{jk}=\frac{dp(k)+(S_k+P)^2-dp(j)+(S_j+P)^2}{2(S_k-S_j)}$,则满足$S_i > k_{jk}$时在$i$处时$k$比$j$优。

总结

斜率优化就是用来解决DP方程中有像$(a_i-a_j)^2$这样与$i, j$都相关的信息的优化,并且满足决策单调性,能够化作斜率式,并且斜率和$x$是单调的。如果斜率不是单调的,就要用二分查找队列中的最优解。如果$x$不是单调的,我们需要使用CDQ分治或者splay来解决这个问题。

斜率横坐标不单增

例题:Bzoj 2726

这里斜率横坐标不单增,所以凸壳左端点不一定为最优决策。
因为对于一条斜率为$k$的直线,将他放到凸壳中的应该排的位置即为最优决策点,所以我们可以不在队首淘汰元素,而是维护整个凸壳,然后在队列里二分找到将他放到凸壳中的应该排的位置即可转移。

常见题型

参考资料

------ 本文结束 ------