Statement
Solution
先考虑最暴力的\(dp\),也就是\(f_i=\max_{j=0}^if_j+a(s_i-s_j)^2+b(s_i-s_j)+c\),其中\(s_i\)表示\(x_i\)的前缀和.
那么此时我们可以把式子拆开,不难发现是要我们维护一个上凸包然后取队首即可.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define re register
#define ll long long
#define int ll
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef pair<int,int> pii;
inline int gi(){
int f=1,sum=0;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
const int N=1000010;
int n,q[N],a,b,c,x[N],s[N],f[N];
int calc(int i,int j){return f[j]+a*sqr(s[i]-s[j])+b*(s[i]-s[j])+c;}
double slope(int i,int j){
int x=s[j],y=f[j]+a*s[j]*s[j]-b*s[j];
int X=s[i],Y=f[i]+a*s[i]*s[i]-b*s[i];
return (double)1.*(Y-y)/(X-x);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=gi();
a=gi();b=gi();c=gi();
for(int i=1;i<=n;i++)x[i]=gi(),s[i]=s[i-1]+x[i];
int h,t;q[h=t=1]=0;
for(int i=1;i<=n;i++){
while(h<t&&calc(i,q[h])<calc(i,q[h+1]))h++;
f[i]=calc(i,q[h]);
while(h<t&&slope(q[t],i)>=slope(q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld\n",f[n]);
return 0;
}