Description

Input

Output

Sample Input

Sample Output

HINT

这是一道DP题，还是比较明显的= =

f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b(sum[i]-sum[j])+c);

然后呢 一看这样的式子我们就可以尝试斜率优化。

设k<j<i

若f[j]>f[k]，则k无用

(f[k]+a*s[k]^2-b*s[k]-f[j]-a*s[j]^2+b*s[k])/2*a*(s[k]-s[j]) <= s[i]

显然就可以斜率优化了

#include <cstdio>
#define maxn 1000010
#define ll long long
ll f[maxn],s[maxn],q[maxn],a,b,c;
ll dy(int x)
{
	return f[x]+a*s[x]*s[x]-b*s[x];
}
ll dx(int x)
{
	return 2*a*s[x];
}

int main()
{
	int n;
	scanf("%d",&n);
	scanf("%lld%lld%lld",&a,&b,&c);
	for (int i = 1;i <= n;i++)
	{
		ll x;
		scanf("%lld",&x);
		s[i] = s[i-1]+x;
	}
	int l = 1,r = 1;
	for (int i = 1;i <= n;i++)
	{
		for (;l<r&&(dy(q[l+1])-dy(q[l]))>=s[i]*(dx(q[l+1])-dx(q[l]));l++);
		f[i] = f[q[l]]+(s[i]-s[q[l]])*(s[i]-s[q[l]])*a+(s[i]-s[q[l]])*b+c;
		for (;l<r&&(dy(i)-dy(q[r]))*(dx(q[r])-dx(q[r-1]))<=(dy(q[r])-dy(q[r-1]))*(dx(i)-dx(q[r]));r--);
		q[++r] = i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

dp提高还是得多艹题！