1 #include
     
       2 #include
      
        3 #define M 1000009 4 #define ll long long 5 using namespace std; 6 int n,zhan[M],h,t; 7 ll a,b,c,f[M],sum[M]; 8 double pai(int a1,int a2) 9 {10     double ss=(f[a1]-f[a2])/(1.0*a*(sum[a2]-sum[a1]));11     return ss-sum[a2]-sum[a1];12 }13 int main()14 {15     scanf("%d%lld%lld%lld",&n,&a,&b,&c);16     for(int i=1;i<=n;i++)17       {18         int a1;19         scanf("%lld",&a1);20         sum[i]=sum[i-1]+a1;21       }22     h=0;23     for(int i=1;i<=n;i++)24       {25         for(;h
       
        =-b/(1.0*a)-2*sum[i];h++);26         f[i]=f[zhan[h]]+a*(sum[zhan[h]]-sum[i])*(sum[zhan[h]]-sum[i])+b*(sum[i]-sum[zhan[h]])+c;27         for(;h
        
         <=pai(zhan[t],i);t--);28         zhan[++t]=i;29       }30     printf("%lld\n",f[n]);31     return 0;32 }
        
       
      
     

普通的斜率优化DP。