f[i]表示前i个人能获得的最大战力。 f[i]=max{f[j]+w(j+1,i)|1<=j< i}.w(j+1,i)表示j+1…i组成一队获得的战斗力,把sum[i]-sum[j]代入公式即可。如果k1< k2且k1优于k2: f[k1]-f[k2]+a*sum[k1]^2-a*sum[k2]^2+b*(sum[k2]-sum[k1])>2*a*(sum[k1]-sum[k2])*sum[i]。还是维护一个下凸曲线，保证队列中的斜率单增。
#include <cstdio> #include <cstring> #define ll long long int const N=1000010; int n,a,b,c,q[N],h=0,t=0; ll f[N],sum[N]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline double slope(int k1,int k2){//注意加括号啊。。 return (f[k1]-f[k2]+a*(sum[k1]*sum[k1]-sum[k2]*sum[k2])+b*(sum[k2]-sum[k1]))*1.0/(2.0*a*(sum[k1]-sum[k2])); } int main(){ // freopen("a.in","r",stdin); n=read();a=read();b=read();c=read(); for(int i=1;i<=n;++i){int x=read();sum[i]=sum[i-1]+x;} for(int i=1;i<=n;++i){ while(h<t&&slope(q[h],q[h+1])<(double)sum[i]) h++; f[i]=f[q[h]]+a*((sum[i]-sum[q[h]])*(sum[i]-sum[q[h]]))+b*(sum[i]-sum[q[h]])+c; while(h<t&&slope(q[t],i)<slope(q[t-1],q[t])) t--; q[++t]=i; } printf("%lld",f[n]); return 0; }