夏晓光(loveJY)的博客

斜率优化好题

首先我们那道题写出状态转移方程后感到了一丝丝不对劲,因为这个式子好像不能直接斜率优化啊?

$f_i=f_j+max(a_k)*max(b_k),j<i,j<=k<=i$

但是我们要斜率优化!!!所以如果我们a和b之和i,j有关就好了

脑袋里浮现出了一个经典的交叉直线:

在矩形的宽递减的同时长递增

如果我们能把序列转换成这样的东西,就能很好去维护转移了!

然后你会敏锐的发现其他长宽严格小于某矩形的矩形一定没用了,因为可以分给这一组然后不产生贡献

所以我们就预处理一下搞出这样的符合的矩形序列

紧接着我们斜率优化走起

$f_j=f_i+a_{i+1}*b_j$

$k=b_{j}$,$x=a_{i+1}$,$x=f_i$,$y=f_j$

直接套板子??不行,想想我们维护的凸包是什么

要解决的是最小化问题,所以我们维护下凸包,然后卡的直线斜率应该刚好大于其中某条

同时呢我们新加入形成的凸包要满足后面的斜率大于前面的,所以如果小于就删掉

写的时候要注意宽是递减的,也就是说求斜率的时候我们应该把分母那个东西改一改...

代码里面为了显得getslope函数正常直接维护了一个负数域的上凸包,以后请不要这样

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int MAXN = 1e5 + 7;
int n, que[MAXN];
struct rec {
	int x, y;
	bool operator<(const rec &w)const {
		return x == w.x ? y > w.y : x > w.x;
	}
} e[MAXN];
ll f[MAXN];
inline int getx(int x) {
	return e[x + 1].x;
}

inline ll gety(int x) {
	return f[x];
}

inline int getk(int x) {
	return e[x].y;
}

inline ll calc(int x, int y) {
	return f[y] + 1ll * e[x].y * e[y + 1].x;
}

inline db getslope(int x, int y) {
	return (1.0 * gety(x) - gety(y)) / (1.0 * getx(x) - getx(y));
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
	}
	sort(e + 1, e + n + 1);
	int m = 0;
	for(int i = 1; i <= n; ++i)
		if(e[i].y > e[m].y)
			e[++m] = e[i];
	n = m;
	// for(int i = 1; i <= n; ++i) {
	// 	printf("%d %d\n", e[i].x, e[i].y);
	// }
	int h = 1, t = 1;
	que[h] = 0;
	for(int i = 1; i <= n; ++i) {
		// printf("%d %d %d %lf %d\n", que[h], que[h + 1], t, getslope(que[h], que[h + 1]), e[i].y);
		while(h < t && getslope(que[h], que[h + 1]) > -e[i].y) {
			// printf("%lf %d\n", getslope(que[h], que[h + 1]), e[i].y);
			++h;
		}
		// printf("calc:%d %d?\n", i, que[h]);
		f[i] = calc(i, que[h]); 
		// printf("%lld???\n", f[i]);
		while(h < t && getslope(que[t - 1], que[t]) < getslope(que[t], i)) {
			// printf("%lf %lf\n", getslope(que[t], que[t - 1]), getslope(que[t], i));
			--t;
		}
		que[++t] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}