斜率优化DP – Solutions

斜率优化是将方程看起来非常可推的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……

fstqwq

Never say die.

斜率优化DP – Solutions

Leave a Reply Cancel reply