「算法笔记」斜率优化

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


单调队列优化

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

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

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

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

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

很显然我们只需要用一个单调队列维护 $f_i+b_i$,每次转移时取出队首元素即可。这样可以将复杂度优化到 $\mathcal 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) $$

直接转移肯定是 $\mathcal 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$ 后,要将当前点插入凸壳中。如果队尾的两条直线不满足斜率递增的话,就可以将队尾元素弹出。

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

由于每个元素只会进队和出队一次,所以时间复杂度为 $\mathcal 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;
}

习题

发表评论