60分求助帖,感觉斜优+单调队列没问题QAQ
查看原帖
60分求助帖,感觉斜优+单调队列没问题QAQ
227725
Liostream楼主2023/1/29 22:36
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=300005;
ll f[M],c[M],t[M],dp[M],s;
int l=1,r=1,q[M],n;
ll A(int x){
	return dp[x]-s*(c[x]);
}
ll B(int x){
	return c[x]*t[x]+s*c[n];
}
int main()
{
	int id;
	scanf("%d",&n);
	cin>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i]>>c[i];
	}
	for(int i=1;i<=n;i++)
	{
		t[i]=t[i-1]+t[i];
		c[i]=c[i-1]+c[i];
	}
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		while(l+1<=r&&(A(q[l+1])-A(q[l]))<=(c[q[l+1]]-c[q[l]])*t[i]) l++;
		id=q[l];
		dp[i]=B(i)+A(id)-c[id]*t[i];
		while(l+1<=r&&(A(i)-A(q[r]))*(c[q[r]]-c[q[r-1]])<=(A(q[r])-A(q[r-1]))*(c[i]-c[q[r]])) r--;
		q[++r]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}
2023/1/29 22:36
加载中...