斜率优化
对于形如
\[
f[i] = \min_{j<i}\{f[j]+a[i]b[j]+c_1[j]\}+c_2[i]
\]
的状态转移方程，且满足 \(a[i],b[i]\) 单调，可以使用斜率优化，将时间复杂度降低到 \(O(n)\)。
整体思路
设 \(j\) 是 \(i\) 的最优决策点，有
\[
f[i]=f[j]+a[i]b[j]+c_1[j]+c_2[i]
\]
移项：
\[
f[i]-c_2[i]=a[i]\big(b[j]\big)+\big(f[j]+c_1[j]\big)
\]
我们可以将每个 \(j<i\) 都看作一个点 \((b[j],f[j]+c_1[j])\)，转移的过程就是拿一条斜率为 \(-a[i]\) 的直线去切这些点。使截距最小化的节点就是最优决策点。
容易发现，最优决策点就是直线和凸包的切点。我们使用单调队列（单调栈）维护这个凸包。同时由于直线的斜率 \(a[i]\) 具有单调性，直接将队首（栈顶）更劣的节点弹出，即可保证队首节点的最优性。
具体的，每遍历到一个 \(i\)，
- 根据斜率找到最优决策点（切点），并将最优决策点之前的所有点都弹出队列；
- 计算当前 DP 值；
- 弹出队尾更劣的节点，更新凸包；
例题
题目大意
给你一个长度为 \(n\) 的数列，第 \(i\) 个数为 \(a_i\)。你需要将这个数列划分为若干连续段。设一个连续段的区间和为 \(s\)，则该连续段的代价为 \((s-L)^2\)，其中 \(L\) 为给定常数。问最小代价和。
我们写出 DP 方程：
\[
f[i]=\min_{j=1}^{i-1}\{f[j]+w(j,i)\}
\]
其中
\[
w(l,r)=(s[r]-s[l]-L)^2\\
s[x]=\sum_{i=1}^{x}{(c[i]+1)}
\]
将方程展开：
\[
f[i]=\min_{j=1}^{i-1}\Big\{f[j]+(s[j]+L)^2-2s[i]\big(s[j]+L\big)\Big\}+s[i]^2
\]
考虑最优决策点 \(j_0\)：
\[
f[i]+2s[i]L-s[i]^2=-2s[i]s[j]+\big(f[j]+(s[j]+L)^2\big)
\]
我们对所有 \((s[j],f[j]+(s[j]+L)^2)\) 维护一个下凸包，转移时用直线 \(y=(2s[i])x\) 切这个凸包，切点即时最优决策点。按上文使用单调队列维护凸包即可。
模板代码
| #include<iostream>
#define int long long
#define ld long double
using namespace std;
const int N = 5E4 + 10;
int n, l;
int s[N], f[N];
inline int pw2(int x) { return x * x; }
inline int X(int i) { return s[i]; }
inline int Y(int i) { return pw2(s[i] + l) + f[i]; }
inline ld K(int i1, int i2) { return (ld)(Y(i2) - Y(i1)) / (X(i2) - X(i1)); }
int que[N];
int head = 1, tail = 0;
signed main() {
cin >> n >> l;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
++x;
s[i] = s[i - 1] + x;
}
que[++tail] = 0;
++l;
for(int i = 1; i <= n; i++) {
while(head < tail && K(que[head], que[head + 1]) <= 2 * s[i]) ++head;
f[i] = f[que[head]] + pw2(s[i] - s[que[head]] - l);
while(head < tail && K(que[tail - 1], i) <= K(que[tail - 1], que[tail])) --tail;
que[++tail] = i;
}
cout << f[n] << endl;
return 0;
}
|
题意
给定一个长为 \(n\) 的序列 \(a\)，要求你将它划分成恰好 \(m\) 段连续的区间，最小化 \(\sum_{i=1}^m{(s[r_i]-s[l_i-1])^2}\)。
我们可以跑 \(m\) 次斜率优化，时间复杂度 \(O(nm)\)。
本题答案关于 \(m\) 具有凸性，可以优化至 \(O(n\log V)\)。做法详见 wqs 二分。
代码
| #include<iostream>
#define int long long
#define ld long double
using namespace std;
const int N = 3010;
const int INF = (int)0x3f3f3f3f3f3f3f3f;
int n, m;
int s[N], f[N], g[N];
inline int pw(int x) { return x * x; }
inline int X(int i) { return s[i]; }
inline int Y(int i) { return f[i] + s[i] * s[i]; }
inline ld K(int i1, int i2) { return (ld)(Y(i2) - Y(i1)) / (X(i2) - X(i1)); }
int que[N];
int head, tail;
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
s[i] = s[i - 1] + x;
}
for(int i = 1; i <= n; i++) f[i] = INF;
for(int k = 1; k <= m; k++) {
head = 1, tail = 0;
que[++tail] = 0;
for(int i = 1; i <= n; i++) {
while(head < tail && K(que[head], que[head + 1]) <= 2 * s[i]) ++head;
g[i] = f[que[head]] + pw(s[i] - s[que[head]]);
while(head < tail && K(que[tail - 1], que[tail]) >= K(que[tail - 1], i)) --tail;
que[++tail] = i;
}
for(int i = 1; i <= n; i++) {
f[i] = g[i];
}
}
cout << f[n] * m - s[n] * s[n] << endl;
return 0;
}
|
代码
| #include<iostream>
#define int long long
#define ld long double
using namespace std;
const int N = 1E6 + 10;
int n, a, b, c;
int s[N], f[N];
inline int pw(int x) { return x * x; }
inline int X(int i) { return s[i]; }
inline int Y(int i) { return f[i] + a * pw(s[i]); }
inline ld K(int i1, int i2) { return (ld)(Y(i2) - Y(i1)) / (X(i2) - X(i1)); }
int que[N];
int head = 1, tail = 0;
signed main() {
cin >> n >> a >> b >> c;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
s[i] = s[i - 1] + x;
}
que[++tail] = 0;
for(int i = 1; i <= n; i++) {
while(head < tail && K(que[head], que[head + 1]) >= 2 * a * s[i]) ++head;
f[i] = f[que[head]] + a * pw(s[i] - s[que[head]]) + c;
while(head < tail && K(que[tail - 1], que[tail]) <= K(que[tail - 1], i)) --tail;
que[++tail] = i;
}
cout << f[n] + b * s[n] << endl;
return 0;
}
|