斜率优化10分求调
查看原帖
斜率优化10分求调
454478
cqbzlzm楼主2023/7/12 16:59


#include<bits/stdc++.h>
using namespace std;
#define MAXN 300000
#define int long long
int n, s;
int t[MAXN + 5], c[MAXN + 5];
int dp[MAXN + 5];
int q[MAXN * 2 + 5];
long double slope(int a, int b) {
	return ((long double)((dp[b] - s * c[b] - dp[a] + s * c[a]) * 1.0)) / (c[b] - c[a]);
}
signed main() {
	scanf("%lld%lld", &n, &s);
	for (int i = 1; i <= n; i ++) {
		scanf("%lld%lld", &t[i], &c[i]);
		t[i] += t[i - 1];
		c[i] += c[i - 1];
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[0] = 0;
//	for (int i = 1; i <= n; i ++) {
//		for (int j = 0; j < i; j ++) {
//			dp[i] = min(dp[i], dp[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]));
//		}
//	}
	int head = 0, tail = 0;
	for (int i = 1; i <= n; i ++) {
		while (head + 1 < tail && slope(q[tail - 1], q[tail - 2]) <= slope(q[tail - 1], i - 1)) {
			tail --;
		}
		q[tail ++] = i - 1;
		while (head + 1 < tail && slope(q[head], q[head + 1]) <= t[i]) {
			head ++;
		}
		int j = q[head];
		dp[i] = dp[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
	}
	printf("%lld", dp[n]);
	return 0;
}
2023/7/12 16:59
加载中...