斜率优化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;

  1. [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;
    }
  2. [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;
    }
    
  3. [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;
    }
    
  4. [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;
    }
    
  5. 防御准备
    #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;
    }
    
  6. [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;
    }
    
  7. 小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;
    }
    
  8. [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……

发表评论

电子邮件地址不会被公开。 必填项已用*标注