50pts求调
查看原帖
50pts求调
482007
TanX_1e18楼主2023/7/5 11:36
#include<bits/stdc++.h>
using namespace std;
long long n,p,q,f[200009][2];
long long q1[200009],h1,d1,minx;
double xielv(int x,int y)
{
	return double(f[x][1]-p*x*x-(f[y][1]-p*y*y))/(2*p*x-2*p*y);
}
int main()
{
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++)
	{
		f[i][1]=minx+q*i;
		while(h1<d1&&i*(2*p*q1[h1+1]-2*p*q1[h1])>=(f[q1[h1+1]][1]-p*q1[h1+1]*q1[h1+1]-(f[q1[h1]][1]-p*q1[h1]*q1[h1])))
		{
			h1++;
		}
		f[i][0]=f[q1[h1]][1]+p*(i-q1[h1])*(i-q1[h1]);
		minx=min(minx,f[i][0]-q*i);
		while(h1<d1&&xielv(q1[d1],q1[d1-1])>=xielv(i,q1[d1]))
		{
			d1--;
		}
		q1[++d1]=i;
	}
	cout<<min(f[n][1],f[n][0]);
	return 0;
}
2023/7/5 11:36
加载中...