斜率优化

ICPC 斜率优化

 2019/04/03 

斜率优化

针对形如：的动态规划转移方程，可通过''斜率''的单调性进行优化。

题一、[HNOI2008]玩具装箱TOY

题意题目链接

给定长为的序列，将序列分成若干连续段，每段的花费为其中为常数，。要求计算总的最小花费代价。

解题思路

利用前缀和，区间序列和可表示成。容易想到 dp 转移方程为：将变量整理归类，记，则转化成：转移方程移项可得：因为在固定时可认为是个定值，故问题相当于最小化，进而可以将问题看成是斜率为的直线，找出一点使得直线在轴的截距最小。

图 1. 下凸壳-灰色点和黑色点分别表示非凸壳点和凸壳点。

显然，截距最小的关键点必然在下凸壳上，且下凸壳的每段斜率是单调递增的。

斜率为的直线截距最小所对应的最优点是，该点前一段斜率，后一段斜率。

注意，斜率是单调递增的，则对应的最优点位置也是单调的，所以这种情况可通过双端队列将复杂度优化到。

题二、小A与最大子段和

题意题目链接

给定长为的序列，找一个非空连续子段，最大化：

解题思路

把问题进一步公式化：为了去除，引入前缀和和，公式 (1) 转化成：根据变量下标整理归类：同"玩具装箱TOY"，此时相当于令截距最大，所以此时需要维护点集的上凸壳。

因为存在负数，故斜率并不具有单调性，所以需要二分确定最优点的位置。

参考

代码

[HNOI2008]玩具装箱TOY

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) begin(x),end(x)
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << "=" << x << ", "
#define de(x) cout << #x << "=" << x << endl
//-------
const int N = 5e5 + 7;
int n, L, C[N];
ll S[N], dp[N];
struct P {
	ll x, y;
	P() {}
	P(ll _x, ll _y) {
		x = _x, y = _y;
	}
	P operator-(const P &p) const {
		return P(x - p.x, y - p.y);
	}
	ll operator^(const P &p) const {
		return x * p.y - y * p.x;		
	}
};
#define X(i) (i + S[i] + L + 1)
#define Y(i) (dp[i] + X(i) * X(i))
int main() {
	scanf("%d%d", &n, &L);
	rep(i, 1, n + 1) scanf("%d", C + i);
	rep(i, 1, n + 1) S[i] = S[i - 1] + C[i];
	deque<P> Q; Q.push_back(P(X(0), Y(0)));
	rep(i, 1, n + 1) {
		ll g = 2 * (i + S[i]);
		while (sz(Q) > 1 && (Q[1].y - Q[0].y) < (Q[1].x - Q[0].x) * g) 
			Q.pop_front();
		dp[i] = Q[0].y - g * Q[0].x + (i + S[i]) * (i + S[i]);
		P a(X(i), Y(i));
		while (sz(Q) > 1 && ((Q[sz(Q) - 2] - a) ^ (Q.back() - a)) <= 0) 
			Q.pop_back();	
		Q.push_back(a);
	}	
	printf("%lld", dp[n]);
	return 0;
}

小A与最大子段和

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) begin(x),end(x)
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << "=" << x << ", "
#define de(x) cout << #x << "=" << x << endl
//-------
const int N = 2e5 + 7;
int n, a[N];
ll S[N], V[N];
#define X(i) (i)
#define Y(i) (i * S[i] - V[i])
struct P {
	ll x, y;
	P() {} P(ll _x, ll _y) { x = _x, y = _y; } 
	P operator-(const P &p) const {
		return P(x - p.x, y - p.y);
	}
	ll operator^(const P &p) const {
		return x * p.y - y * p.x;
	}
};
bool chk(deque<P> &Q, int i, ll G) {
	return (Q[i + 1].y - Q[i].y) >= (Q[i + 1].x - Q[i].x) * G;	
}
int main() {
	scanf("%d", &n);
	rep(i, 1, n + 1) scanf("%d", a + i);	
	rep(i, 1, n + 1) S[i] = S[i - 1] + a[i];
	rep(i, 1, n + 1) V[i] = V[i - 1] + i * a[i];
		
	deque<P> Q; Q.push_back(P(X(0), Y(0)));
	ll ans = LLONG_MIN;
	rep(i, 1, n + 1) {
		// answer
		int l = 0, r = max(0, sz(Q) - 2);
		while (l + 1 < r) {
			int z = (l + r) >> 1;
			chk(Q, z, S[i]) ? l = z : r = z;	
		}
		int j = l;
		if (chk(Q, r, S[i])) j = r + 1;
		else if (chk(Q, l, S[i])) j = l + 1;
		else j = l;
		ll f = Q[j].y - S[i] * Q[j].x + V[i];
		ans = max(ans, f);
		// maintain
		P a(X(i), Y(i));
		while (sz(Q) > 1 && ((Q[sz(Q) - 2] - a) ^ (Q.back() - a)) >= 0)
			Q.pop_back();
		Q.push_back(a);
	}
	printf("%lld", ans);
	return 0;
}