夏晓光(loveJY)的博客

靠这题搞事情啊???

你会发现是经典题目斜率优化,然后我们$T_i$不是单调的...

写出dp式子,转换成斜率优化形式

$dp_{i}-Sc_i*St_i+Sc_j*St_i=dp_j+s*(Sc_n-Sc_j)$

你会发现b是$dp_{i}-Sc_i*St_i$,然后k是$St_i$,x是$Sc_j$,y是$dp_j+s*Sc_j$

(常数我们直接吃掉)

也就是说我们每次去切的直线斜率不是单调的,但是我们横坐标还是单调递增的!

所以我们可以维护整个凸包,然后每次找最优决策点的时候二分,找到第一个直线斜率大于他的,然后前面点就是答案

即mid,mid+1斜率大于他,那么一定是和这个直线产生交点.....

然后我们上凸点还是没用的,所以仍然能维护凸包

实现细节:

1. 卡精度要叉积判,nmd叉积判是要判断x差正负号的QAQAQAQ,但是x是单增的我们尽量让他是正的....
2. 二分的时候我们要返回的是决策点,套que
3. 维护凸包的while不要写错了

code

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int MAXN = 5e5 + 7;
int t[MAXN], c[MAXN], St[MAXN], Sc[MAXN];
int que[MAXN], ex, n, l, r;
ll f[MAXN];

inline ll gx(int x) {
	return Sc[x];
}

inline ll gy(int x) {
	return f[x]  - ex * Sc[x];
}

//常数在b里,吃掉了
//判断(x->y)<(x->y)
inline int pdslope(int x, int y, int z) {
	// bool flg = 0;
	// ll tmp1 = gx(x) - gx(z);
	// // flg ^= (tmp1 < 0);
	// ll tmp2 = gx(y) - gx(x);
	// flg ^= (tmp2 < 0);
	// printf("%lld %lld %lld")
	// printf("slope:%lld %lld??%lld %lldby : %lld %lld %lld\n", gy(x) - gy(z), gy(y) - gy(x), tmp1, tmp2, z, x, y);
	// if(flg)return (gy(y) - gy(x)) * tmp1 > (gy(z) - gy(x)) * tmp2;
	return 	(gy(x) - gy(z)) * (gx(y) - gx(x)) >= (gy(y) - gy(x)) * (gx(x) - gx(z));
}

inline ll calc(int x, int y) {
	return f[y] + St[x] * (Sc[x] - Sc[y]) + ex * (Sc[n] - Sc[y]);
}

inline int solve(ll x) {
	int L = l, R = r - 1, ret = -1, mid;
	// printf("!in the erfen");
	while(L <= R) {
		mid = (L + R) >> 1;
		// printf("but :%lld %lld %lld %lld\n", L, R, gy(que[mid + 1]) - gy(que[mid]), x * (gx(que[mid + 1]) - gx(que[mid])));
		if(gy(que[mid + 1]) - gy(que[mid]) > x * (gx(que[mid + 1]) - gx(que[mid]))) {
			ret = mid;
			R = mid - 1;//再靠后显然不行!
		} else
			L = mid + 1;
	}
	if(ret == -1)return que[r];
	return que[ret];
}

signed main() {
	scanf("%lld", &n);
	scanf("%lld", &ex);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &t[i], &c[i]);
		St[i] = St[i - 1] + t[i];
		Sc[i] = Sc[i - 1] + c[i];
	}
	memset(f, 0x3f3f3f3f, sizeof(f));
	l = 0, r = 0;
	f[0] = que[0] = 0;
	for(int i = 1; i <= n; ++i) {
		int j = solve((long double)St[i]);
		f[i] = calc(i, j);
		// printf("we are %lld  by %lld getvalue:%lld\n", i, bst, f[i]);
		// printf("in ?%lld?%lld %lld %lld\n", l, r, que[l], que[r]);
		while(l < r && pdslope(que[r], i, que[r - 1])) {//前小于后
			--r;
		}
		que[++r] = i;
	}
	printf("%lld\n", f[n]);
	return 0;
}