首先定义f[i]为前i个士兵组成的最大战斗力
直接计算的方式
for(int i=1;i<=n;++i)for(int j=0;j<i;++j)f[i]=max(f[i],f[j]+calc(c[i]-c[j]));
其中calc为计算二次函数的值 c[i]为预处理的前缀和
这样只能得到50分，我们还需要继续进行斜率优化
设j的方案比k更优，有
整理得
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,x[maxn];
long long f[maxn],s[maxn],c[maxn];
int A,B,C;
long long calc(long long x)
{return x*x*A+x*B+C;
}
double count(long long j , long long k)
{return (f[j]-B*c[j]+A*c[j]*c[j]-f[k]-A*c[k]*c[k]+B*c[k])/(2.0*A*(c[j]-c[k]));
}
int main()
{freopen("a.in","r",stdin); freopen("a.out","w",stdout);scanf("%d%d%d%d",&n,&A,&B,&C);for(int i=1;i<=n;i++) scanf("%d",&x[i]);for(int i=1;i<=n;i++) c[i]=c[i-1]+x[i];for(int i=1;i<=n;i++) f[i]=-1e18;int h=0,t=0;for(int i=1;i<=n;i++){while(h<t && count(s[h],s[h+1])<=c[i]*1.0) h++;f[i]=f[s[h]]+calc(c[i]-c[s[h]]);while(h<t && count(s[t-1],s[t])>=count(s[t],i)) t--;s[++t]=i;}printf("%lld\n",f[n]);return 0;
}