题意
给定一个长度为 $n$ 的序列，每个元素有权值 $x_i$，现在要将序列分割为若干段，每段中元素连续。设 $s_i$ 表示前缀和，即 $s_i=\sum_{j=1}^{i}{x_j}$，那么对于每段 $[l, r]$，代价为：
a(s_{i}-s_{j-1})^2+b(s_i-s_{j-1})+c
$$
其中 $a, b, c$ 为题目给定的常数。整个序列的代价为每段代价之和。
求序列的代价最大值。
$1\leq n\leq 10^6, -{10}^7\leq b, c\leq 10^7, 1\leq x_i\leq 100$.
注意：$-5\leq \textcolor{red}{a} \leq -1\textcolor{red}{<0}$.
DP
容易想到时间复杂度为 $\mathcal{O}(n^2)$ 的 DP 做法。
令 $f_i$ 为前 $i$ 个物品，分若干段的最小代价，有状态转移方程：
f_i=\max_{j<i}{\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}}
$$
其中 $s_i$ 与题目中定义相同，为 $x$ 的前缀和。
但发现 $1\leq n\leq 10^6$，所以这样的 DP 无法通过此题，考虑如何优化。
优化
发现对于 $f_i$ 来说，一定存在唯一的 $j<i$ 对=”” $f_i$=”” 进行了更新，使得=”” 取到最大值。所以不妨设=”” $j$=”” 为能<strong=””>使 $f_i$ 最大化的继承状态， 那么对暴力的状态转移方程进行整理：</i$>
\begin{aligned}
f_i&=f_j+a(s_i-s_j)^2+b_(s_i-s_j)+c\\
f_i&=f_j+a({s_i}^2+{s_j}^2-2s_is_j)+b(s_i-s_j)+c\\
f_i&=f_j+a\cdot {s_i}^2+a\cdot {s_j}^2-2a\cdot s_is_j+b\cdot s_i-b\cdot s_j+c
\end{aligned}
$$
（这就很斜率优化
考虑一次函数的斜截式 $y=kx+b$，将方程转化为这个形式。其中变量 $x, y$ 与 $j$ 有关，$b, k$ 与 $j$ 无关，且要求 $x$ 随 $j$ 单调递增。
那么：
\textcolor{red}{f_i-b\cdot s_i-a\cdot {s_i}^2}=\textcolor{purple}{(f_j+a\cdot {s_j}^2-b\cdot s_j+c)}-\textcolor{green}{2a\cdot s_i}\textcolor{blue}{s_j}
$$
所以：
\left\{
\begin{array}{lr}
y = f_j+a\cdot {s_j}^2-b\cdot s_j+c\\
k = 2a\cdot s_i\\
x = s_j\\
b = f_i-b\cdot s_i-a\cdot {s_i}^2
\end{array}
\right.
$$
观察 $b$ 这一项。要最大化 $f_i$，而 $-b\cdot s_i-a\cdot{s_i}^2$ 为常数，所以只要最大化 $b$ 即可。
由于 $x, y$ 只与 $j$ 有关，不妨设 $(x_j, y_j)$ 为平面直角坐标系上的一些点。那么问题就转化为，如何选取 $j$，才能使得，斜率固定为 $k$ 的，且过点 $(x_j, y_j)$ 的直线的截距 $b$ 最大。
（斜率为定值 $k$，是因为 $2a\cdot s_i$ 也都是题目给定的定值。
那么问题转化到了平面上。
由上图可以形象的看出，使直线截距最大的点（最优决策点），就是将直线向下平移时第一个碰到的点。
而且显然对于任意的斜率 $k$ 来说，最优决策点只有可能在上凸包上，也就是上图中，绿色直线所覆盖的点。
继续观察，在上图中可以看出，对于斜率为 $k$ 的直线，最优解 $j$ 就是第一个 $\operatorname{slope}{(j, j+1)} < k$ 的点。（$\operatorname{slope}(a, b)$ 表示 $(x_a, y_a), (x_b, y_b)$ 两点构成直线的斜率）
又因为本题中，$k$ 随 $i$ 递增而递减，与上凸包单调性相同，所以考虑使用单调队列解决。
单调队列
设单调队列（递增）为 $q$，队首为 $head$，队尾为 $tail$，当前要转移 $i$ 号点，具体步骤：
- 当 $\operatorname{slope}(q_{head}, q_{head+1})\textcolor{red}{\geq}2a\cdot s_i$ 时，$head$++，（保证最优解）
- 此时的 $q_{head}$ 就是最优转移点，根据它和转移方程计算出 $f_i$，
- 当 $\operatorname{slope}(q_{tail-1}, q_{tail})\textcolor{red}{\leq}\operatorname{slope}(q_{tail}, i)$ 时，$tail$–，（维护上凸包）
- 在队尾插入 $i$.
代码
注意多组数据即可。
#include <bits/stdc++.h>
#define int long long
#define x(X) (s[X])
#define y(X) (f[X] + a * s[X] * s[X] - b * s[X] + c)
using namespace std;
const int MAXN = 1e6 + 10;
int n;
int a, b, c;
int s[MAXN], f[MAXN];
int head, tail, q[MAXN];
double slope(int i, int j) {
return 1.0 * (y(j) - y(i)) / (x(j) - x(i));
}
signed main() {
int T; scanf("%lld", &T);
while(T--) {
scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
for(int i = 1; i <= n; i++) {
int tmp; scanf("%lld", &tmp);
s[i] = s[i - 1] + tmp;
}
head = tail = 1;
for(int i = 1; i <= n; i++) {
while(head < tail && slope(q[head], q[head + 1]) >= 2ll * a * s[i])
head++;
int j = q[head];
f[i] = f[j] + a * (s[i]-s[j])*(s[i]-s[j]) + b*(s[i]-s[j]) + c;
while(head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i))
tail--;
q[++tail] = i;
}
cout << f[n] << endl;
}
return 0;
}