来自 这篇笔记 第6部分。

题目链接：AcWing luogu

题意

有一支由 $n$ 名士兵组成的部队，士兵从 $1$ 到 $n$ 编号，要将他们拆分成若干个特别行动队调入战场。同一支行动队的队员的编号应该连续。

编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支队伍的初始战斗力为所有队员初始战斗力之和，记为 $x$ 。最终战斗力为：$x’=ax^2+bx+c.(a<0)$.

试求出最终战斗力之和的最大值。

思路

令 $s[i]=\sum_{j=1}^i x_j.$
$$ f[i]=f[j]+a\times (s[i]-s[j])^2+b\times (s[i]-s[j])+c. \\\\ =f[j]+as[i]^2-2as[i]s[j]+as[j]^2+bs[i]-bs[j]+c \\\\ =(f[j]+as[j]^2-bs[j])+(as[i]^2+bs[i]+c)-2as[i]s[j] $$
所以整合得到：
$$ f[j]+as[j]^2-bs[j]=2as[i]s[j]+(f[i]-as[i]^2-bs[i]-c) $$

代码

#include <bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const int N=1e6+10;
int n,q[N],h,t;
ll s[N],a,b,c,f[N];

ll X( int num ){ return s[num]; }
ll Y( int num ){ return f[num]+a*s[num]*s[num]-b*s[num]; }
lb slope( int n1,int n2 ) { return (lb)(Y(n2)-Y(n1))/(X(n2)-X(n1)); }

int main()
{
        scanf( "%d",&n ); scanf( "%lld%lld%lld",&a,&b,&c );
        s[0]=0;
        for ( int i=1; i<=n; i++ )
                scanf( "%lld",&s[i] ),s[i]+=s[i-1];

        h=t=1; q[1]=0;
        for ( int i=1; i<=n; i++ )
        {
                while ( h<t && slope(q[h],q[h+1])>=(lb)2.0*a*s[i] ) h++;
                int j=q[h]; f[i]=f[j]+a*s[j]*s[j]-b*s[j]+a*s[i]*s[i]+b*s[i]+c-2*a*s[i]*s[j];
                while ( h<t && slope(q[t-1],q[t])<=slope(q[t],i) ) t--;
                t++; q[t]=i;
        }

        printf( "%lld",f[n] );
}