Description

Input

Output

Sample Input

4

-1 10 -20

2 2 3 4

Sample Output

9

 

 

 

斜率优化 推式子

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=1e6+10;long long n,a,b,c,sum[maxn],yy[maxn],zz[maxn],l=1,r=0,dp[maxn]; long long aa,fl;char cc;long long read() { aa=0;cc=getchar();fl=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') fl=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa*fl;} bool ok(long long x,long long y,long long z) { return (yy[y]-yy[x])*(sum[z-1]-sum[y-1])<(yy[z]-yy[y])*(sum[y-1]-sum[x-1]);} int main() { n=read();a=read();b=read();c=read(); for(int i=1;i<=n;++i) sum[i]=read(),sum[i]+=sum[i-1]; for(int i=1;i<=n;++i) { yy[i]=a*sum[i-1]*sum[i-1]-b*sum[i-1]+dp[i-1]; while(l
            
             -2*a*sum[i]*sum[zz[l]-1]+yy[zz[l]]) l++; dp[i]=-2*a*sum[i]*sum[zz[l]-1]+yy[zz[l]]+a*sum[i]*sum[i]+b*sum[i]+c; } printf("%lld",dp[n]); return 0;}