题目描述

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

出于默契的考虑，同一支行动队的队员的编号应该连续。

编号为 $i$ 的士兵的初始战斗力为 $x_i$，一支行动队的初始战斗力为队内所有队员初始战斗力之和。

通过长期观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下公式修正为 $x'$：

$$x' = a x^2 + b x + c$$

其中，$a, b, c$ 是已知的系数（$a < 0$）。

作为部队统帅，你要为这支部队进行编队，使得所有特别行动队修正后的战斗力之和最大。

试求出这个最大和。

输入格式

第一行包含一个整数 $n$，表示士兵总数。

第二行包含三个整数 $a, b, c$。

第三行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示每名士兵的初始战斗力。

输出格式

输出一个整数，表示战斗力之和的最大值。

样例

4 
-1 10 -20 
2 2 3 4 

9

样例解释

数据

• $n = 4$
• $a = -1, b = 10, c = -20$
• 士兵战斗力：$[2, 2, 3, 4]$

计算

设前缀和 $s[i]$ 表示前 $i$ 个士兵战斗力之和，$s[0]=0$。 $s[1]=2, s[2]=4, s[3]=7, s[4]=11$。

行动队必须是连续编号的，设 $dp[i]$ 表示前 $i$ 个士兵编队的最大修正战斗力之和。

考虑将最后一段行动队设为 $[j+1, i]$，其初始战斗力为 $x = s[i] - s[j]$，修正后为 $a x^2 + b x + c$。

转移方程：

$$dp[i] = \max_{0 \le j < i} \{ dp[j] + a (s[i] - s[j])^2 + b (s[i] - s[j]) + c \}$$

手动计算

$dp[0] = 0$

$i=1$（前 1 个士兵）：

• $j=0$：$dp[0] + a(2)^2 + b(2) + c = 0 + (-1)\times4 + 10\times2 -20 = -4+20-20 = -4$ $dp[1] = -4$

$i=2$（前 2 个士兵）：

• $j=0$：$0 + a(4)^2 + b(4) + c = (-1)\times16 + 40 -20 = -16+40-20=4$
• $j=1$：$dp[1] + a(2)^2 + b(2) + c = -4 + (-4)+20-20 = -8$ $dp[2] = 4$

$i=3$（前 3 个士兵）：

• $j=0$：$0 + a(7)^2 + b(7) + c = (-1)\times49 + 70 -20 = -49+70-20=1$
• $j=1$：$-4 + a(5)^2 + b(5) + c = -4 + (-25)+50-20 = 1$
• $j=2$：$4 + a(3)^2 + b(3) + c = 4 + (-9)+30-20 = 5$ $dp[3] = 5$

$i=4$（前 4 个士兵）：

• $j=0$：$0 + a(11)^2 + b(11) + c = (-121)+110-20 = -31$
• $j=1$：$-4 + a(9)^2 + b(9) + c = -4 + (-81)+90-20 = -15$
• $j=2$：$4 + a(7)^2 + b(7) + c = 4 + (-49)+70-20 = 5$
• $j=3$：$5 + a(4)^2 + b(4) + c = 5 + (-16)+40-20 = 9$ $dp[4] = 9$

因此最大和为 $9$。

编队方案

从 $j=3$ 转移过来，即最后一段是 $[4,4]$（士兵 4 单独一队），前面 $[1,3]$ 为一队。

• 前 3 个士兵：战斗力 $2+2+3=7$，修正后 $(-1)\times49 + 10\times7 -20 = -49+70-20=1$
• 士兵 4：战斗力 4，修正后 $(-1)\times16 + 10\times4 -20 = -16+40-20=4$ 总和 $1+4=5$？不对，上面计算 $dp[3]=5$，但 $dp[3]$ 表示前 3 个士兵最优编队值，我们这里假设 $[1,3]$ 为一队得到 1，但 $dp[3]$ 最优是 5（即 $[1,3]$ 可以再细分得到更大值）。

实际最优编队： 从 $dp[4]$ 的转移看，$j=3$ 时 $dp[3]=5$，最后一段 $[4,4]$ 修正值 4，总和 9。 那么 $dp[3]=5$ 对应的编队是？ $dp[3]$ 从 $j=2$ 转移：$dp[2]=4$，最后一段 $[3,3]$ 修正值 $a(3)^2+b(3)+c = -9+30-20=1$，总和 5。 $dp[2]=4$ 从 $j=0$ 转移：$dp[0]=0$，最后一段 $[1,2]$ 修正值 $a(4)^2+b(4)+c = -16+40-20=4$。 因此编队为：

• $[1,2]$ 一队：修正值 4
• $[3,3]$ 一队：修正值 1
• $[4,4]$ 一队：修正值 4 总和 $4+1+4=9$。

验证：

• $[1,2]$ 初始战斗力 4，修正：$-1\times16+10\times4-20= -16+40-20=4$
• $[3,3]$ 初始 3，修正：$-9+30-20=1$
• $[4,4]$ 初始 4，修正：$-16+40-20=4$ 总 $4+1+4=9$，正确。

数据范围

• $1 \le n \le 10^6$
• $-5 \le a \le -1$
• $|b|, |c| \le 10^7$
• $1 \le x_i \le 100$

算法分析

朴素 DP

设 $s[i] = \sum_{k=1}^i x_k$，$dp[i]$ 表示前 $i$ 个士兵编队的最大修正战斗力之和。

转移：

$$dp[i] = \max_{0 \le j < i} \{ dp[j] + a (s[i] - s[j])^2 + b (s[i] - s[j]) + c \}$$

直接计算复杂度 $O(n^2)$，$n$ 最多 $10^6$，会超时。

斜率优化

将转移方程展开：

$$dp[i] = \max_{0 \le j < i} \{ dp[j] + a s[i]^2 - 2a s[i] s[j] + a s[j]^2 + b s[i] - b s[j] + c \}$$

将只与 $i$ 有关的项提出来：

$$dp[i] = a s[i]^2 + b s[i] + c + \max_{0 \le j < i} \{ dp[j] - 2a s[i] s[j] + a s[j]^2 - b s[j] \}$$

令 $y_j = dp[j] + a s[j]^2 - b s[j]$，$x_j = s[j]$，$k_i = 2a s[i]$（注意 $a<0$，$k_i$ 随 $s[i]$ 增加而减少，即斜率递减）。

则：

$$dp[i] = a s[i]^2 + b s[i] + c + \max_{0 \le j < i} \{ y_j - k_i x_j \}$$

问题转化为：对于每个 $i$，在已知的点集 $(x_j, y_j)$ 中，找到使 $y_j - k_i x_j$ 最大的 $j$。

即对于一条斜率为 $k_i$ 的直线，从上方经过点集，最大化截距。

由于 $k_i$ 单调递减（因为 $a<0$，$s[i]$ 单调递增），$x_j$ 单调递增，可以使用单调队列维护凸包（下凸壳？注意是最大化截距，直线斜率为负且递减，应维护上凸壳）。

具体来说：

• 我们需要维护一个上凸壳（相邻点斜率递减）。
• 对于每个 $i$，在队列头部删除斜率大于 $k_i$ 的点（因为最优点的斜率应小于等于 $k_i$），队头即为最优点。
• 将新点 $(x_i, y_i)$ 加入队列尾部，删除队尾破坏凸性的点。

斜率判断

设队列中连续三点 $j_1, j_2, j_3$，$j_2$ 应被删除当且仅当：

$$\frac{y_{j_2} - y_{j_1}}{x_{j_2} - x_{j_1}} \le \frac{y_{j_3} - y_{j_2}}{x_{j_3} - x_{j_2}}$$

（维护上凸壳，斜率递减，如果出现递增则删除中间点）

取队头条件

队头两点 $j_1, j_2$，若 $\frac{y_{j_2} - y_{j_1}}{x_{j_2} - x_{j_1}} \ge k_i$，则 $j_1$ 不如 $j_2$ 优，弹出 $j_1$。

因为最大化 $y - k x$，当斜率 $k$ 递减时，最优点的斜率应小于等于 $k_i$。

初始化

队列中加入点 $(0, 0)$（对应 $j=0$，$s[0]=0, dp[0]=0, y_0=0$）。

复杂度

每个点进出队列一次，总复杂度 $O(n)$。

注意事项

• 使用 long long 类型，因为中间结果可能很大。
• 注意 $a<0$，斜率 $k_i = 2a s[i]$ 为负数且递减（更负）。
• 除法判断斜率时注意转为乘法避免精度问题。