斜率优化是将方程看起来非常可推的dp从\( O(n^2) \)优化至\( O(n) \)的优秀方法,这种优化是基于决策单调性的……………………
一句话:都是套路。
关于斜率优化的文章很多,而且我数学贼差QAQ(主要是懒),就直接指向一篇本校神犇HenryPigLi的斜率优化DP,虽然他推得有点乱但是还算能看。
然而他的文章还有一个好,就是底下给的题比其他blog都多,于是我觉得应该把solution发出来。
P.S. 这些代码开头都长这样,所以就单独写出来了:
/* Never Say Die. */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <ctime> #include <cstdlib> using namespace std; int _c = 0; template <class _T> inline void read(_T &_a) { _a = 0; bool _f = 0; while (_c < '0' || _c > '9') _f |= _c == '-', _c = getchar(); while (_c >= '0' && _c <= '9') _a = _a * 10 + _c - '0', _c = getchar(); if (_f) _a = -_a; } typedef long long LL; typedef long double LD;
- [HNOI2008]玩具装箱
#define MAXN 50005 int n, L; LL c[MAXN], s[MAXN], h[MAXN], f[MAXN]; LL power(LL x) {return x * x;} LD slope(int j, int k) { return (f[j] + power(s[j] + L) - f[k] - power(s[k] + L)) / (s[j] - s[k]); } struct monoQueue { int v[MAXN], l, r; void maintain(int i) { while (l < r && slope(v[l], v[l + 1]) <= 2 * s[i]) l++; } void insert(int x) { while (l < r && slope(v[r], x) <= slope(v[r], v[r - 1])) r--; v[++r] = x; } } q; int main() { read(n); read(L); ++L; for (int i = 1; i <= n; i++) read(c[i]), s[i] = s[i - 1] + c[i] + 1; for (int i = 1; i <= n; i++) { q.maintain(i); int j = q.v[q.l]; f[i] = f[j] + power(s[i] - s[j] - L); q.insert(i); } printf("%lld\n", f[n]); return 0; }
- [ZJOI2007]仓库建设
#define MAXN 1000005 int n, x[MAXN]; LL c[MAXN], s[MAXN], f[MAXN], C[MAXN]; LD slope(int j, int k) { return LD(f[j] + s[j] - f[k] - s[k]) / LD(c[j] - c[k]); } struct monoQueue { int v[MAXN], l, r; void maintain(int i) { while (l < r && slope(v[l], v[l + 1]) < x[i]) l++; } void insert(int i) { while (l < r && slope(v[r - 1], v[r]) > slope(v[r], i)) r--; v[++r] = i; } } q; int main() { read(n); for (int i = 1, j; i <= n; i++) read(x[i]), read(j), read(C[i]), c[i] = c[i - 1] + j, s[i] = s[i - 1] + (LL)j * x[i]; for (int i = 1; i <= n; i++) { q.maintain(i); int j = q.v[q.l]; f[i] = f[j] + (c[i] - c[j]) * x[i] - (s[i] - s[j]) + C[i]; q.insert(i); } printf("%lld\n", f[n]); return 0; }
- [USACO2008 Mar]土地购买
#define MAXN 50005 struct Rect { int x, y; bool operator < (Rect a) const { if (x != a.x) return x < a.x; else return y < a.y; } } a[MAXN], sta[MAXN]; int n, m = 0; LL f[MAXN], xx[MAXN], yy[MAXN]; LD slope(int u, int v) { return LD(f[u] - f[v]) / (yy[v] - yy[u]); } struct monoQueue { int l, r; int v[MAXN]; int &operator [] (int x) {return v[x];} void maintain(int x) { while (l < r && slope(v[l], v[l + 1]) < xx[x]) l++; } void insert(int x) { while (l < r && slope(x, v[r]) < slope(v[r], v[r - 1])) r--; v[++r] = x; } } s; int main() { read(n); for (int i = 1; i <= n; i++) read(a[i].x), read(a[i].y); sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { while (m && a[i].y >= sta[m].y) m--; sta[++m] = a[i]; } for (int i = 1; i <= m; i++) { xx[i] = sta[i].x; yy[i - 1] = sta[i].y; } f[0] = 0; for (int i = 1; i <= m; i++) { s.maintain(i); int to = s[s.l]; f[i] = f[to] + xx[i] * yy[to]; s.insert(i); } printf("%lld\n", f[m]); return 0; }
- [Apio2010]特别行动队
#define MAXN 1000005 int n; LL A, B, C, s[MAXN], f[MAXN], y[MAXN]; LD slope(int j, int k) { return LD(y[j] - y[k]) / LD(s[j] - s[k]); } LL calc(LL x) { return A * x * x + B * x + C; } struct monoQueue { int v[MAXN], l, r; void maintain(int i) { while (l < r && slope(v[l], v[l + 1]) > 2 * A * s[i]) l++; } void insert(int i) { while (l < r && slope(v[r], i) > slope(v[r], v[r - 1])) r--; v[++r] = i; } } q; int main() { read(n); read(A); read(B); read(C); for (int i = 1, ai; i <= n; i++) {read(ai); s[i] = s[i - 1] + ai;} for (int i = 1; i <= n; i++) { q.maintain(i); int j = q.v[q.l]; f[i] = f[j] + calc(s[i] - s[j]); y[i] = f[i] + A * s[i] * s[i] - B * s[i]; q.insert(i); } printf("%lld\n", f[n]); return 0; }
- 防御准备
#define MAXN 1000005 int n; LL f[MAXN], a[MAXN]; LD slope(int j, int k) { return LD(2 * f[j] + (LL)j * j + j - 2 * f[k] - (LL)k * k - k) / (j - k); } struct monoQueue { int v[MAXN], l, r; void maintain(int i) { while (l < r && slope(v[l], v[l + 1]) < 2 * i) l++; } void insert(int i) { while (l < r && slope(v[r], i) < slope(v[r], v[r - 1])) r--; v[++r] = i; } } q; int main() { read(n); for (int i = 1; i <= n; i++) read(a[i]); for (int i = 1; i <= n; i++) { q.maintain(i); int j = q.v[q.l]; f[i] = f[j] + LL(i - j) * (i - j - 1) / 2 + a[i]; q.insert(i); } printf("%lld\n", f[n]); return 0; }
- [Apio2014]序列分割
#define MAXN 100005 int n, K, a[MAXN]; LL f[MAXN][2], s[MAXN], rs[MAXN]; LD slope(int i, int j, int k) { return LD(f[j][i] - f[k][i]) / (s[j] - s[k]); } struct monoQueue { int v[MAXN], l, r; void clear() { l = r = v[0] = 0; } void maintain(int k, int i) { while (l < r && slope(k, v[l], v[l + 1]) > rs[i]) l++; } void insert(int k, int i) { while (l < r && slope(k, v[r], i) > slope(k, v[r - 1], v[r])) r--; v[++r] = i; } int front() {return v[l];} } q[2]; int main() { read(n); read(K); for (int i = 1; i <= n; i++) { read(a[i]); if (a[i] == 0) {i--, n--; continue;} s[i] = s[i - 1] + a[i]; } K = min(K, n - 1); for (int i = 0; i <= n; i++) rs[i] = s[n] - s[i]; for (int k = 1; k <= K; k++) { int now = k & 1, pre = now ^ 1; q[now].clear(); for (int i = 1; i < n; i++) { q[pre].maintain(pre, i); int j = q[pre].front(); f[i][now] = f[j][pre] + (s[i] - s[j]) * rs[i]; q[now].insert(now, i); } } LL ans = 0; for (int i = K; i < n; i++) ans = max(ans, f[i][K & 1]); printf("%lld\n", ans); return 0; }
- 小P的牧场
#define MAXN 1000005 int n; LL a[MAXN], s[MAXN], b[MAXN], f[MAXN]; LD slope(int j, int k) { return LD(f[j] + b[j] - f[k] - b[k]) / (s[j] - s[k]); } struct monoQueue { int v[MAXN], l, r; void maintain(int i) { while (l < r && slope(v[l], v[l + 1]) < i) l++; } void insert(int i) { while (l < r && slope(v[r], i) < slope(v[r - 1], v[r])) r--; v[++r] = i; } int front() { return v[l]; } } q; int main() { read(n); for (int i = 1; i <= n; i++) read(a[i]); for (int i = 1; i <= n; i++) read(b[i]), s[i] = s[i - 1] + b[i], b[i] = b[i - 1] + b[i] * i; for (int i = 1; i <= n; i++) { q.maintain(i); int j = q.front(); f[i] = f[j] + i * (s[i] - s[j]) - (b[i] - b[j]) + a[i]; q.insert(i); } printf("%lld\n", f[n]); return 0; }
- [SDOI2016]征途
#define MAXN 3005 int n, m; LL L, d[MAXN], f[2][MAXN]; LL power(LL x) {return x * x;} LD slope(int i, int j, int k) { return LD(f[i][j] + 2 * L * d[j] + m * power(d[j]) - f[i][k] - 2 * L * d[k] - m * power(d[k])) / (d[j] - d[k]); } struct monoQueue { int v[MAXN], l, r; void clear() {v[0] = l = r = 0;} void maintain(int k, int i) { while (l < r && slope(k, v[l], v[l + 1]) <= 2 * m * d[i]) l++; } void insert(int k, int i) { while (l < r && slope(k, v[r], i) <= slope(k, v[r - 1], v[r])) r--; v[++r] = i; } int front() {return v[l];} } q[2]; int main() { read(n); read(m); for (int i = 1, ai; i <= n; i++) read(ai), d[i] = d[i - 1] + ai; L = d[n]; for (int k = 1; k <= m; k++) { int now = k & 1, pre = now ^ 1; q[now].clear(); for (int i = 1; i <= n; i++) { q[pre].maintain(pre, i); int j = q[pre].front(); f[now][i] = f[pre][j] + m * power(d[i] - d[j]) - 2 * L * (d[i] - d[j]); q[now].insert(now, i); } } printf("%lld\n", f[m & 1][n] + power(L)); return 0; }
不知不觉我已经成为压行狂魔了QAQ……