设$s[i]$为战斗力前缀和
显然我们可以列出方程
$f[i]=f[j]+a*(s[i]-s[j])^{2}+b*(s[i]-s[j])+c$
$f[i]=f[j]+a*s[i]^{2}+b*s[i]-(2*a*s[i]+b)*s[j]+a*s[j]^{2}+c$
$a*s[j]^{2}+f[j]=(2*a*s[i]+b)*s[j]+f[i]-a*s[i]^{2}-b*s[i]-c$
又变成了喜闻乐见的$y=k*x+b$
$y=a*s[j]^{2}+f[j]$
$k=2*a*s[i]+b$
$x=s[j]$
$b=f[i]-a*s[i]^{2}-b*s[i]-c$
$x,k$都是单调
于是再来个熟悉的单调队列维护上凸包就好辣
使用叉积判断斜率大小会爆long long，请使用正常的斜率判断
#include<iostream> #include<cstdio> #include<cstring> #define rint register int using namespace std; typedef long long ll; typedef double db; #define N 1000005 ll n,a,b,c,w,s[N],f[N]; int L=1,R=1,h[N]; inline db X(int i){return s[i];} inline db Y(int i){return a*s[i]*s[i]+f[i];} inline ll KK(ll xa,ll ya,ll xb,ll yb){return ya*xb-xa*yb;}//数据过大，叉积爆炸 inline db K(int x,int y){return (Y(x)-Y(y))/(X(x)-X(y));} int main(){ //freopen("P3628.in","r",stdin); scanf("%lld%lld%lld%lld",&n,&a,&b,&c); for(rint i=1;i<=n;++i) scanf("%lld",&s[i]),s[i]+=s[i-1]; for(rint i=1;i<=n;++i){ while(L<R&&K(h[L],h[L+1])>=2*a*s[i]+b) ++L; w=s[i]-s[h[L]]; f[i]=f[h[L]]+a*w*w+b*w+c; while(L<R&&K(h[R],h[R-1])<=K(h[R],i)) --R; h[++R]=i; }printf("%lld",f[n]); return 0; }
原文：https://www.cnblogs.com/kafuuchino/p/10752999.html