---

Solution

设 $f[x]$ 表示特别行动队前 $x$ 名士兵编好队的最大战斗力。

$$f[x]=max^{i-1}_{k=0}f_k+a[A(i)-A(k)]^x+b[A(i)-A(k)]+c$$
化简、移项：得到斜率方程：

$$f[k]-f[j]+a[A^2(k)-A^2(j)]-b[A(k)-A(j)]>2aA(i)·[A(k)-A(j)]$$
然后就可以斜率优化了。

---

Code

#include <iostream>
#include <cstdio>#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Pow(x) ((x)*(x))using namespace std;LL n,a,b,c,Max_Right,Lastcost,INF=9223372036854777LL;LL A[1000010],As[1000010];
LL f[1000010],fs[1000010];
double ks[1000010];inline void in(LL &x){char ch=getchar();x=0;LL flag=1;while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')flag=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=flag;
}double get_y(LL x){return (double)f[x]/(2*a)+(double)Pow(A[x])/2-(double)b*A[x]/(2*a);
}double get_k(LL x,LL y){return (double)((double)fs[x]/(2*a)+(double)Pow(As[x])/2-(double)b*As[x]/(2*a)-get_y(y))/(As[x]-A[y]);
}int main(){freopen("commando.in","r",stdin);freopen("commando.out","w",stdout);in(n);in(a);in(b);in(c);for(LL i=1,tmp;i<=n;i++){in(tmp);A[i]=A[i-1]+tmp;}ks[Max_Right]=-INF;ks[Max_Right+1]=INF;for(LL i=1;i<=n;i++){for(LL j=Lastcost;j<=Max_Right;j++)if(A[i]>=ks[j]&&A[i]<=ks[j+1]){Lastcost=j;f[i]=fs[j]+a*Pow(A[i]-As[j])+b*(A[i]-As[j])+c;break;}for(LL k=Max_Right;k>=0;k--){double tmp=get_k(k,i);if(tmp>=ks[k]){Max_Right=k+1;ks[k+1]=tmp;ks[k+2]=INF;fs[k+1]=f[i];As[k+1]=A[i];Lastcost=Min(Lastcost,Max_Right);break;}}}printf("%lld\n",f[n]);return 0;
}