又是斜率dp= =

f[i]=MAX(f[x]+a*sqr(f[i]-f[x])+b*(f[i]-f[x])+c)

设对于f[x] f[i]+a*sqr(s[x]-s[i])+b*(s[x]-s[i])+c>f[j]+a*sqr(s[x]-s[j])+b*(s[x]-s[j])+c

整理得 (v(i)-v[j])/(s[i]-s[j])<2a*s[x]  (v[x]=f[x]+a*s[x]*s[x]-b*s[x])

然后就证明s[x]单调

就行了

CODE：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

#define maxn 1000010

long long f[maxn],sum[maxn];

int s[maxn],a,b,c,n;

long long v(int x,int y){

 return (f[x]+a*sum[x]*sum[x]-b*sum[x])-(f[y]+a*sum[y]*sum[y]-b*sum[y]);

}

int main(){

 scanf("%d",&n);

 scanf("%d%d%d",&a,&b,&c);

 for (int i=1;i<=n;i++) {

  int x;

  scanf("%d",&x);

  sum[i]=sum[i-1]+x;

 }

 s[1]=0;

 int h=1,t=1;

 for (int i=1;i<=n;i++){

  while (h<t&&v(s[h],s[h+1])<=2*a*sum[i]*(sum[s[h]]-sum[s[h+1]]))h++;

  f[i]=f[s[h]]+a*(sum[i]-sum[s[h]])*(sum[i]-sum[s[h]])+b*(sum[i]-sum[s[h]])+c;

  while (h<t&&v(s[t],i)*(sum[s[t-1]]-sum[s[t]])>=v(s[t-1],s[t])*(sum[s[t]]-sum[i])) t--;

  s[++t]=i;

 }

 printf("%lld\n",f[n]);

 return 0;

}