斜率优化求调【悬赏5关注】
查看原帖
斜率优化求调【悬赏5关注】
490978
小超手123楼主2023/2/26 15:01
#include<bits/stdc++.h>
#define int long long
#define N 300005
using namespace std;
int n, s;
int t[N], f[N]; 
int dp[N], Q[N], head = 1, tail = 0;
double slope(int x, int y) {
	return 1.0000 * (dp[y-1] - dp[x-1]) / (f[y-1] - f[x-1]);
}
signed main() {
	cin >> n >> s;
	for(int i = 1; i <= n; i++) {
		cin >> t[i] >> f[i];
		t[i] += t[i-1];
		f[i] += f[i-1];
		dp[i] = 1e15;
	}
	dp[1] = t[1] * f[1] + s * f[n];
	Q[++tail] = 1;
	for(int i = 2; i <= n; i++) {
		while(head < tail && slope(Q[head+1], Q[head]) < t[i] + s) head++;
		int j = Q[head];
		dp[i] = dp[j-1] + t[i] * (f[i] - f[j-1]) + s * (f[n] - f[j-1]);
		while(head < tail && slope(Q[i], Q[tail]) < slope(Q[tail], Q[tail-1])) tail--;
		Q[++tail] = i;
	}
	cout << dp[n];
    return 0;
}
2023/2/26 15:01
加载中...