題意

你有一支由 $n$ 名預備役士兵組成的部隊，士兵從 $1$ 到 $n$ 編號，你要將他們拆分成若干特別行動隊調入戰場。出于默契的考慮，同一支特別行動隊中隊員的編號應該連續，即為形如 $i,i+1,?,i+k$的序列。所有的隊員都應該屬于且僅屬于一支特別行動隊。

編號為 $i$ 的士兵的初始戰斗力為 $x_i$ ，一支特別行動隊的初始戰斗力 $X$ 為隊內士兵初始戰斗力之和，即 $X=x_i+x_{i+1}+?+x_{i+k}$。

通過長期的觀察，你總結出對于一支初始戰斗力為 $X$ 的特別行動隊，其修正戰斗力 $X^{\prime }=a{X}^2+bX+c$，其中 $a,b,c$ 是已知的系數。 作為部隊統帥，現在你要為這支部隊進行編隊，使得所有特別行動隊的修正戰斗力之和最大。試求出這個最大和。

$1\le n\le 10^6$，$?5\le a\le ?1$，$?10^7\le b,c\le 10^7$，$1\le x_i\le 100$。

思路

先考慮樸素的 dp，令 $f_i$ 表示將前 $i$ 個人分隊完畢的最大戰斗力，設：
$$s_i=\sum _{j=1}^i{x}_i,z(x)=a{x}^2+bx+c$$

那么有：
f i = max ? j ∈ [ 1 , i ) { f j + z ( s i ? s j ) } f_i=\max_{j\in[1,i)}\left \{f_j+z(s_i-s_j)\right \} fi?=j∈[1,i)max?{fj?+z(si??sj?)}

去到了 $\Theta (n^2)$ 級別。由上一篇題解的經驗，考慮使用斜率優化掉找 $j$ 的 $\Theta (n)$：

設有決策點 $j1$ 和 $j2$ 且 $j2$ 優于 $j1$，那么：
$$f_{j1}+z(s_i?s_{j1})\le f_{j2}+z(s_i?s_{j2})$$

$$f_{j1}+a(s_i?s_{j1}{)}^2+b(s_i?s_{j1})\le f_{j2}+a(s_i?s_{j2}{)}^2+b(s_i?sj2)$$

$$f_{j1}+a{s}_i^2+a{s}_{j1}^2?2a{s}_i{s}_{j1}+b{s}_i?b{s}_{j1}\le f_{j2}+a{s}_i^2+a{s}_{j2}^2?2a{s}_i{s}_{j2}+b{s}_i?b{s}_{j2}$$

$$f_{j1}?f_{j2}?b{s}_{j1}+b{s}_{j2}+a{s}_{j1}^2?a{s}_{j2}^2\le 2a{s}_i{s}_{j1}?2a{s}_i{s}_{j2}$$

$$f_{j1}?f_{j2}?b(s_{j1}?s_{j2})+a(s_{j1}^2?s_{j2}^2)\le 2a{s}_i(s_{j1}?s_{j2})$$

因為 $s_{j1}<s_{j2}$，因而注意變號：
$$\frac{f_{j1}?f_{j2}?b(s_{j1}?s_{j2})+a(s_{j1}^2?s_{j2}^2)}{2a(s_{j1}?s_{j2})}\ge s_i$$

那就不妨拿個 $g_i=a{s}_i^2+b{s}_i$ 來代換了：
$$\frac{f_{j1}?f_{j2}+g_{j1}?g_{j2}}{2a(s_{j1}?s_{j2})}\ge s_i$$

斜率 $slope\ge s_i$，$s_i$ 單增，由下圖，扔到符合條件區間的尾巴去。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
const ll N=1e6+9,inf=0x3f3f3f3f;
ll n,a,b,c,x[N];
ll s[N],g[N],f[N],q[N];
ll _2(ll x)
{return x*x;
}
ll z(ll x)
{return a*_2(x)+b*x+c;
}
dd slope(ll j1,ll j2)
{return (dd)(f[j1]-f[j2]+g[j1]-g[j2])/(dd)(2*a*(s[j1]-s[j2]));
}
int main()
{scanf("%lld%lld%lld%lld",&n,&a,&b,&c);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);s[i]=s[i-1]+x[i];g[i]=a*_2(s[i])-b*s[i];}memset(f,-inf,sizeof(f));ll hh=0,tt=0;f[0]=0;for(int i=1;i<=n;i++){while(hh<tt&&slope(q[hh],q[hh+1])<=s[i])hh++;//slope>s[i]單增，扔隊尾 f[i]=f[q[hh]]+z(s[i]-s[q[hh]]);while(hh<tt&&slope(q[tt],i)<slope(q[tt-1],q[tt]))tt--;q[++tt]=i;}printf("%lld",f[n]);return 0;
}