「算法笔记」斜率优化

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

单调队列优化

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

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

$f_i=\min\{f_j+a_i+b_j\}\quad(0\le j <i)$

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

$f_i=\min\{f_j+b_j\}+a_i$

很显然我们只需要用一个单调队列维护 $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$ 个单词的最小代价，很容易写出如下方程：

$\text{我们记}\ sum_k=\sum_{i=1}^k C_i \\ \text{转移方程为}\ f_i=\min\{f_j+(sum_i-sum_j)^2+M\}\quad (0\le j <i)$

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

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

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

$f_k+(sum_i-sum_k)^2+M\ge f_j+(sum_i-sum_j)^2+M$

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

$\begin{aligned} f_k+(sum_i-sum_k)^2+M &\ge f_j+(sum_i-sum_j)^2+M \\ f_k+(sum_i-sum_k)^2 &\ge f_j+(sum_i-sum_j)^2 \\ f_k+{sum_k}^2-2\cdot sum_i\cdot sum_k&\ge f_j+{sum_j}^2-2\cdot sum_i\cdot sum_j \\ 2\cdot sum_i (sum_j-sum_k)&\ge (f_j+{sum_j}^2)-(f_k+{sum_k}^2) \end{aligned}$

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

$2\cdot sum_i\ge \frac{(f_j+{sum_j}^2)-(f_k+{sum_k}^2)}{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)$。

伪代码

代码

#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;
}

单调队列优化

斜率优化

分析

引理

实现

伪代码

代码

习题