斜率优化42求调
查看原帖
斜率优化42求调
484788
suzhui楼主2024/11/6 13:10

题目不能下载数据,不知道问题在哪,求各位大佬调一下
orz

#include<bits/stdc++.h>
using namespace std;
const int m=22000;
int n,p,q;
double k[m],lk;
long long w[m],d[m],f[m],x[m],y[m],ans=2e9,sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p>>q;
		for(int j=i;j<=n;j++)w[j]+=p;
		for(int j=1;j<=i;j++)d[j]+=q;
	}
	for(int i=2;i<=n;i++){
		f[1]+=(w[i]-w[i-1])*d[i];
	}
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+w[i-1]*(d[i-1]-d[i])-(w[i]-w[i-1])*d[i];
	}
	x[1]=w[1],y[1]=f[1],k[1]=-1e3;
	p=2;
	for(int i=2;i<=n;i++){
		int flag=0;
		while(flag==0){
			lk=(y[p-1]-f[i])*1.0/(x[p-1]-w[i]);
			if(lk>0)flag=1;
			else if(lk>k[p-1])x[p]=w[i],y[p]=f[i],k[p]=lk,p++,flag=1;
			else p--;
		}
		lk=-d[i];
		for(int j=1;j<p;j++){
			if(lk<k[j]){
				q=j-1;
				break;
			}
		} 
		sum=y[q]-lk*x[q]-w[i]*d[i];
		ans=min(ans,sum);
	}
	cout<<ans;
}
2024/11/6 13:10
加载中...