令 \(f_i\) 表示前 \(i\) 个士兵组成特别行动队的最大修正战斗力之和。对 \(x\) 做一遍前缀和。

转移方程：

\[f_i=\max\{f_j+a\times(x_i-x_j)^2+b\times(x_i-x_j)+c|j<i\} \]

考虑两个决策 \(j,k(j<k)\)，若 \(j\) 比 \(k\) 优：

\[f_j+a\times(x_i-x_j)^2+b\times(x_i-x_j)+c>f_k+a\times(x_i-x_k)^2+b\times(x_i-x_k)+c \]

\[f_j-f_k>a\times(x_i^2-2\times x_i\times x_k+x_k^2-x_i^2+2\times x_i\times x_j-x_j^2)+b\times(x_i-x_k-x_i+x_j) \]

\[f_j-f_k>a\times x_k^2+2a\times x_i\times x_j-2a\times x_i\times x_k-a\times x_j^2+b\times x_j-b\times x_k \]

\[f_j+a\times x_j^2-b\times x_j-f_k-a\times x_k^2+b\times x_k>x_i\times(2a\times x_j-2a\times x_k) \]

\[\dfrac{f_j+a\times x_j^2-b\times x_j-f_k-a\times x_k^2+b\times x_k}{2a\times x_j-2a\times x_k}>x_i \]

两个负的负负得正不用变号。因为 \(x_i\) 随着 \(i\) 的增大单调递增，所以对 \((2a\times x_i,f_i+a\times x_i^2-b\times x_i)\) 维护一个上凸包。

时间复杂度 \(O\left(n\right)\)。