斜率优化dp,求调
查看原帖
斜率优化dp,求调
526895
WYZ20030051楼主2023/5/7 08:57

大佬们,为什么输出的答案不对,感觉写的没有问题(太蒻

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
#define ll long long
const int MAXN=1e6+10;
int n;
int x[MAXN];
int s[MAXN];//前缀和 
ll f[MAXN];//f[i]表示对于1~i的所有x[i],已经分好组的最大和 
int q[MAXN];//数组模拟队列 
int a,b,c;
#define K(i) (2.0*a*s[i])//方便表示 
#define X(i) (s[i])
#define Y(i) (f[i]+a*s[i]*s[i]-b*s[i])
double slope(int a,int b)//斜率 
{
	return 1.0*(Y(b)-Y(a))/(X(b)-X(a));
}
int main()
{
	scanf("%d",&n);
	scanf("%d%d%d",&a,&b,&c);
	s[0]=q[0]=f[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x[i]);
		s[i]=s[i-1]+x[i];
	}
	int head=0,tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail && slope(q[head],q[head+1])>K(i))
			++head;
		f[i]=-(K(i)*X(q[head])-Y(q[head])-a*s[i]*s[i]-b*s[i]-c);
		while(head<tail && slope(q[tail-1],q[tail])<=slope(q[tail],i))
			--tail;
		q[++tail]=i;
	}
	printf("%lld",f[n]);
	return 0;
}
2023/5/7 08:57
加载中...