「算法笔记」斜率优化

斜率优化,一种根据决策单调性来优化动态规划的思想。

单调队列优化

毕竟斜率优化根据的是决策单调性,那么在讲斜率优化前,我们先提一下单调队列优化。

如果我们有一个转移方程:

我们直接转移的复杂度 $O(n^2)$ 的。我们可以把这个方程变形得到:

很显然我们只需要用一个单调队列维护 $f_i+b_i$,每次转移时取出队首元素即可。这样可以将复杂度优化到 $O(n)$,具体方法不再赘述。


斜率优化

当 $\text{DP}$ 方程中有 $a_i\times b_j$ 之类的项时,之前的单调队列优化就不再适用了,所以我们要引入斜率优化。

分析

首先我们看这样一道题目:

一篇文章共有 $n$ 个单词,第 $i$ 个单词有一个权值 $C_i$。一行中可以打印连续的若干个单词,代价是这些单词的权值和的平方加上常数 $M$。要求最小化代价和。

数据范围:$1\le n\le 5\times 10^5$,$0\le M\le 1000$,$1\le C_i\le 10^9$

我们定义 $f_i$ 表示考虑到第 $i$ 个单词的最小代价,很容易写出如下方程:

直接转移肯定是 $O(n^2)$ 的。现在我们有一个很自然的想法:对于每个 $i$,去掉一些不必要的 $j​$ 的枚举。

接下来我们研究一下对于怎么样的 $j$ 是不必要的

任取 $j,k$ 且满足 $0\le k<j<i$,如果此时 $j$ 比 $k$ 要更好,那么有如下不等式:

我们对这个不等式进行变形:

由于权值 $C_i$ 为正整数,所以 $sum_j>sum_k$,可以将 $sum_j-sum_k$ 这一项直接移到右侧,得到:

对于每个元素,我们令 $y_i=f_i+{sum_i}^2$,$x_i=sum_i$。那么上面的式子就可以看成是当 $2\cdot sum_i\ge\text{两个点的斜率}$ 时,选编号大的点更优。

引理

为了方便表述,我们定义 $K(i,j)$ 表示 $i,j$ 两点的斜率

接下来我们要证明: 如果 $i,j,k$ 满足 $k<j<i$ 且 $K(i,j)<K(j,k)$,则 $j$ 永远不可能成为最优解。

  • 当 $K(i,j)\le 2\cdot sum_i$ 时,选择 $i$ 优于选择 $j$,排除 $j$。
  • 当 $K(i,j)>2\cdot sum_i$ 时,选择 $j$ 优于选择 $i$,又因为 $K(j,k)>K(i,j)>2\cdot sum_i$,所以选择 $k$ 优于选择 $j$,同样排除 $j$。

所以假设成立。

实现

我们考虑维护一个斜率递增的凸壳

根据:通过引理,我们可以得出当 $k<j<i$ 时,如果 $K(i,j)<K(j,k)$ 则 $j$ 永远不可能成为最优解,所以有效的点集应该是呈现下凸的性质

每次查询时,用 $2\cdot sum_i$ 去修正队首直线(队首的两个元素组成的直线),如果 $2\cdot sum_i\ge\text{第一个条直线的斜率}$,那么我们就将队首的元素弹出。

根据:因为 $sum_i$ 是递增的,如果此时这条直线的斜率不满足条件,那么它将永远不合法。

更新完队首后,现在的队首就是用来转移 $f_i$ 的最优的 $j$。

根据:两个点 $j,k\ (j<k)$ 满足 $j$ 比 $k$ 更优,当且仅当 $2\cdot sum_i\ge j\ \text{和}\ k\ 两点的斜率$。

计算完 $f_i$ 后,要将当前点插入凸壳中。如果队尾的两条直线不满足斜率递增的话,就可以将队尾元素弹出。

根据:同样依据引理可以得到斜率是单调递增的。

由于每个元素只会进队和出队一次,所以时间复杂度为 $O(n)$。

伪代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>

const int N=5e5+5;
int n,m,c[N],q[N];
long long sum[N],f[N];

double get(int x) {
return 1.0*f[x]+1.0*sum[x]*sum[x];
}
double slope(int i,int j) {
return 1.0*(get(i)-get(j))/(sum[i]-sum[j]);
}
long long sqr(long long x) {
return x*x;
}
int main() {
while(~scanf("%d%d",&n,&m)) {
for(int i=1;i<=n;++i) scanf("%d",&c[i]),sum[i]=sum[i-1]+c[i];
int l=1,r=0;
f[0]=q[++r]=0;
for(int i=1;i<=n;++i) {
while(l<r&&slope(q[l],q[l+1])<=2.0*sum[i]) ++l;
f[i]=f[q[l]]+sqr(sum[i]-sum[q[l]])+m;
while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
q[++r]=i;
}
printf("%lld\n",f[n]);
}
return 0;
}

习题

0%