Meaning
很多时候的 \(dp\) ,大概都是一个这样的式子:
虽然普通决策单调性很好用是没错吧 = = ,但是对于有些题来说,首先 \(cost\) 函数不一定满足四边形不等式,其次决策单调性只适用于取 \(Min\) 的题目,再次决策单调性总要带个 \(log\) ,有时还不是最优秀的解法。
那么由数形结合衍生出来的决策单调性的一个分支就出来了:斜率优化。
对于斜率优化的题目,都满足决策单调性的 \(g[i]\ge g[i-1]\) 。不过我们可以做到 \(O(1)\) 取得决策点 。
General
那么如何优化呢?很简单,从 \(cost\) 函数下手,我们设两个决策点 \(j,k\) 且有 \(j>k\) ,那么我们判断在什么情况下选 \(j\) 比选 \(k\) 更优。
即 \(f[j]+cost[i,j]\le or\ge f[k]+cost[i,k]\) ,在这种情况下,我们将 \(cost\) 函数展开,一般情况下 \(cost\) 函数总是带着和 \(i\) 有关的项,我们将这些项全部移到一边,其他项移到不等式另一边,再将系数除过去,那么就会得到一个等式:某个与 \(i\) 有关的函数 \(\le\) \(\frac{Sth}{Other\ things}\) 。
接着我们发现右边的式子的求法就像斜率一样,那么可知,当两个决策之间满足这个不等式的时候,选 \(j\) 会比选 \(k\) 更优。则我们 \(dp\) 时可以维护一个单调队列,队列中相邻两项的斜率递增或递减,具体根据不等式另一边的函数递增还是递减。
这样讲还是讲不清楚的,结合具体题目来看最好。
Example1-[CEOI2004]锯木厂选址
Problem
有 \(n\) 颗树,它们在一条直线上顺序分布,\(d[i]\) 为第 \(i\) 棵树到第 \(i+1\) 棵树的距离,\(w[i]\) 为每棵树的重量,\(d[n]\) 是第 \(n\) 棵树到旧锯木厂的距离。要求选定两个位置建造新锯木厂,每棵树都会运到右边离它最近的锯木厂。
总花费为每棵树的重量×它到右边最近锯木厂的距离
之和 。
\(n\le 20000\) 。
First Mentality
首先观察到一个异常显然的伪 \(dp\) :设 \(f[i]\) 为在第 \(i\) 棵树建造第二所新锯木厂的最小花费,\(tot\) 为不建造锯木厂的总花费,\(dis[i]\) 为 \(i\) 到旧锯木厂的距离,\(q[i]\) 为 \(w\) 的前缀和,则有:
答案则是 \(Min(dp[i])\) 。
但是 \(n^2\) 的复杂度显然要蛋糕。
斜率优化
我们发现,如果有 \(j>k\) ,且从 \(j\) 转移过来要比 \(k\) 更优,那么意味着有如下不等式:
通过移项得到:
则如果 \(j\) 与 \(k\) 满足这个不等式的话,从 \(j\) 转移必定比从 \(k\) 转移更优。
由于我们枚举 \(i\) 的时候从左往右,则 \(dis[i]\) 是递减的,那么如果 \(j\) 与 \(k\) 的这个不等式当前时候满足了,之后的 \(dp\) 过程中也必定会满足。
所以这个 \(dp\) 满足决策单调性,且与之前的 \(dp\) 值无关,于是我们可以用决策单调性分治来做。
但是用决策单调性做太没技术含量了,毕竟 \(O(nlog)<O(n)\) ,我们来玩斜率优化吧。
对于每个点 \(j\) 我们可以看做二维平面上的一个横坐标为 \(dis[j]*q[j]\) ,纵坐标为 \(q[j]\) 的点,那么对于这个式子 \(\frac{dis[j]*q[j]-dis[k]*q[k]}{q[j]-q[k]}\) ,我们可以理解为直线 \(kj\) 的斜率。
由于 \(dis[i]\) 是单调递减的,则我们对斜率的要求也是单调递减,那么我们用一个单调队列维护这些决策点,保证队列内的斜率单调递减就好了。
第一次接触斜率的话建议瞅瞅代码。
Code
\(work(i,j)\) 代表计算决策点 \(i,j\) 之间的斜率。
#include <cstdio>
#include <iostream>
using namespace std;
int n, head, tail, tot, Ans = 2e9, w[20001], d[20002], q[20002], que[20001];
double work(int a, int b) {
return 1.0 * (q[b] * d[b] - q[a] * d[a]) / (q[b] - q[a]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &d[i]);
for (int i = n; i >= 1; i--) d[i] += d[i + 1];
for (int i = 1; i <= n; i++) q[i] = q[i - 1] + w[i], tot += w[i] * d[i];
for (int i = 1; i <= n; i++) {
while (head < tail && work(que[head], que[head + 1]) > d[i])
head++; //如果队首斜率满足要求,则 head+1 会优于 head
int x = que[head];
Ans = min(Ans, tot - q[x] * d[x] - d[i] * (q[i] - q[x]));
while (head < tail && work(que[tail - 1], que[tail]) < work(que[tail], i))
tail--; //单调队列保证斜率单调递减,则如果尾部斜率小于 i 的斜率,弹掉它
que[++tail] = i;
}
cout << Ans;
}
Example2-[SDOI2016]征途
Problem
给出一段序列,要求连续划分成 \(m\) 段,每一段的值为段内元素之和。
要求使这 \(m\) 段的方差最小,输出最小方差×\(m^2\) 的值。
\(m\le n\le3000\)
First Mentality
我们划分成 \(m\) 段,设第 \(i\) 段的值表示为 \(a_i\) ,平均数表示为 \(average\) ,首先我们来看看方差的式子:
一看就很仙,我们还是先化化简吧,我们的答案还要乘上 \(m^2\) ,目的就是为了使结果为整数,那么我们化简成不带分数的形式总是没错的 \(QwQ\) 。
接下来由于总共有 \(m\) 段,我们把 \(\sum\) 里的定项拆出来。
然后我们把 \(average\) 展开,并设 \(\sum a_i=sum\) ,则 \(average=\frac{sum}{m}\) 写成正常的式子:
然后减去同类项就行了:
那么式子就化简完了,由于 \(sum^2\) 和 \(m\) 都是个定值,所以我们还是只要关心 \(\sum a_i^2\) 最小就行了。
那么思路很明显了:设 \(f[i][j]\) 为选到第 \(i\) 个数,已经划分成了 \(j\) 段的最小值,设第 \(i\) 位的前缀和为 \(q[i]\) 那么不难想到方程如下:
不过这样转移是 \(n^3\) 的,有待优化。
斜率优化
熟悉的套路的推式子环节来啦!
首先嘛,我们发现 \(f[i][j]\) 的转移只与 \(f[k][j-1]\) 有关,那么我们可以用 \(f[i]\) 表示目前第 \(j\) 层的 \(dp\) 值,\(g[i]\) 表示第 \(j-1\) 层的 \(dp\) 值,滚动优化一下空间。
设从 \(j\) 转移比从 \(k\) 转移更优,且 \(j>k\) ,则有:
展开平方并移项:
那么最后我们得到了这个快乐的斜率式。
由于 \(q[i]\) 递增,那么这个 \(dp\) 就符合决策单调性,\(j\) 点一时优,那么就永远优于 \(k\) ,我们设 \(s[i]\) 为 \(f[i]\) 的最优决策点,那么显而易见的 \(s[i]\ge s[i-1]\) ,辣么由于转移的式子与 \(f[j]\) 无关,我们还是可以用决策单调性分治, 我们就自由了很多。
所以维护一个斜率递增的单调队列就行。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, head, tail, a[3001], que[3001];
long long q[3001], f[3001], g[3001];
long double work(int a, int b) {
return 1.0 * (q[b] * q[b] + g[b] - q[a] * q[a] - g[a]) /
(2 * q[b] - 2 * q[a]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
q[i] = q[i - 1] + a[i], g[i] = q[i] * q[i];
}
for (int j = 2; j <= m; j++) {
head = tail = 1;
que[head] = j - 1;
for (int i = j; i <= n; i++) {
while (head < tail && work(que[head], que[head + 1]) < q[i]) head++;
int x = que[head];
f[i] = g[x] + (q[i] - q[x]) * (q[i] - q[x]);
while (head < tail && work(que[tail - 1], que[tail]) > work(que[tail], i))
tail--;
que[++tail] = i;
}
for (int i = 1; i <= n; i++) g[i] = f[i];
}
cout << 1ll * f[n] * m - q[n] * q[n];
}