单调队列优化
毕竟斜率优化根据的是决策单调性，那么在讲斜率优化前，我们先提一下单调队列优化。
如果我们有一个转移方程：
$$ 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;
}
1 条评论
赞赞赞