初学斜率优化求助下owo,WA
查看原帖
初学斜率优化求助下owo,WA
264548
Tangent233楼主2021/12/19 15:02
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
long long dp[maxn],st[maxn],sf[maxn],s,n;
int q[maxn],l=1,r=0;
double slope(int i,int j)
{
	return ((double)dp[i]-dp[j]+s*(sf[j]-sf[i]))/(double(sf[i]-sf[j]));
}
int binary(long double k)
{
	int L=l,R=r,ans=-1;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(slope(q[mid],q[mid+1])>=k)
		{
			ans=mid;
			R=mid-1;
		}
		else L=mid+1;
	}
	if(ans==-1) return r;
	return ans;
}
int main()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		int t,f;cin>>t>>f;
		st[i]=st[i-1]+t;
		sf[i]=sf[i-1]+f;
	}
	dp[0]=q[++r]=0;
	for(int i=1;i<=n;i++)
	{
		//while(l<r&&slope(q[l],q[l+1])<=st[i]) ++l;
		int k=binary((double)st[i]);
		dp[i]=dp[q[k]]+st[i]*(sf[i]-sf[q[k]])+s*(sf[n]-sf[q[k]]);
		while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
		q[++r]=i;
	}
	cout<<dp[n];
	return 0;
}

40ptsqaq

2021/12/19 15:02
加载中...