C++(g++ 7.5.0) 解法, 执行用时: 112ms, 内存消耗: 23384K, 提交时间: 2022-10-11 19:43:51

//dp[i]=max{dp[j]+(a*(sum[i]-sum[j])^2-b*sum[j]))}+c+b*sum[i]
//a*sum[j]^2+dp[j]-b*sum[j]=2*a*sum[i]*sum[j]-a*sum[i]^2-b*sum[i]+dp[i]-c
#include<iostream>
#include<algorithm>
#include<cstring>
#define endl "\n"
using namespace std;
using ll = long long;
const int maxn = 1e6 + 10;
ll sum[maxn],dp[maxn],q[maxn];
ll n,a,b,c,x;
inline ll pow2(ll num)
{
    return num*num;
}
inline ll func(int i)
{
    return a*pow2(sum[i])-b*sum[i]+dp[i];
}
long double slope(int i,int j)
{
    return (long double)(func(i)-func(j))/(long double)(sum[i]-sum[j]);
}
void solve(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    int head=1,tail=1;
    q[1]=0;
    for(int i=1;i<=n;i++)
    {
        while(head<tail&&slope(q[head+1],q[head])>=(2.0*a*sum[i]))
        {
            head++;
        }
        dp[i]=dp[q[head]]+a*pow2(sum[i]-sum[q[head]])+b*(sum[i]-sum[q[head]])+c;
        while(head<tail&&slope(q[tail],q[tail-1])<=slope(i,q[tail]))
        {
            tail--;
        }
        q[++tail]=i;
    }
    cout<<dp[n]<<endl;
}
int main(void)
{
    solve();
    return 0;
}

C++(clang++11) 解法, 执行用时: 115ms, 内存消耗: 15112K, 提交时间: 2020-10-21 19:08:22

#include<bits/stdc++.h>
#define k(i,j) 1.0*(y[j]-y[i])/(x[j]-x[i])
using namespace std;
const int nn=1001021;
int n,a,b,c,j,i,q[nn];
long long f,sumx,x[nn],y[nn];
int main(){
	scanf("%d%d%d%d",&n,&a,&b,&c);
	while(n--){
		if(j>=i)j=i;
		scanf("%lld",x+(++i)),x[i]=sumx=sumx+x[i];
		if(j>=i)j=i;
		else while(j<i-1&&k(j,j+1)>2*x[i]*a)j++;
		f=y[j]+x[i]*x[i]*a-2*x[i]*x[j]*a+x[i]*b+c;
		y[i]=f+x[i]*x[i]*a-x[i]*b;
		for(;k(i-2,i-1)<=k(i-2,i);i--)
			swap(x[i],x[i-1]),swap(y[i],y[i-1]);
	}return printf("%lld",f),0;
}