显然的斜率优化DP

设 $f[i]$ 表示以 i 作为一段区间的结尾，从 1 到 i 的序列的战斗力的最大值

然后枚举上一个结尾 j

设战斗力前缀和为 sum

那么 $f[i]=f[j]+A(sum[i]-sum[j])^2+B(sum[i]-sum[j])+C$

$f[i]= f[j]+ Asum[i]^2 + Asum[j]^2 - 2Asum[i]sum[j] + Bsum[i] - Bsum[j] + C$

$2Asum[i]sum[j] + f[i]-Asum[i]^2-C = f[j]+Asum[j]^2-Bsum[j]$

$k=2Asum[i],x=sum[j],b=f[i]-Asum[i]^2,y=f[j]+Asum[j]^2-Bsum[j]$

然后直接斜率优化

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;typedef long double ldb;inline int read(){ register int x=0,f=1; static char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=2e6+7;int n,A,B,C;ll sum[N],f[N];inline ll X(int i) { return sum[i]; }inline ll Y(int i) { return f[i]+A*sum[i]*sum[i]-B*sum[i]; }inline ldb slope(int i,int j) { return (ldb)(Y(i)-Y(j))/(X(i)-X(j)); }int Q[N],l=1,r=1;int main(){ n=read(),A=read(),B=read(),C=read(); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read(); for(int i=1;i<=n;i++) { while( l