题目描述
原题来自：APIO 2010
你有一支由
n
n 名预备役士兵组成的部队，士兵分别编号为
1\dots n
1…n，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如
(i,
(i,
i + 1,
i+1,
\dots,
…,
i + k)
i+k) 的序列。 编号为
i
i 的士兵的初始战斗力为
x_i
xi
，一支特别行动队的初始战斗力
x
x 为队内士兵初始战斗力之和，即
x = x_i + x_{i+1} +
x=xi
+xi+1
+
\dots + x_{i+k}
⋯+xi+k
。
通过长期的观察，你总结出一支特别行动队的初始战斗力
x
x 将按如下经验公式修正为
x':x'= ax^2+bx+c
x
′
:x
′
=ax2+bx+c ，其中
a, b, c
a,b,c 是已知的系数
(a < 0)
(a<0)。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。
例如，你有 4 名士兵，
x_1 = 2,
x1
=2,
x_2 = 2,
x2
=2,
x_3 = 3,
x3
=3,
x_4 = 4
x4
=4 。经验公式中的参数为
a = –1,
a=–1,
b = 10,
b=10,
c = –20
c=–20。此时，最佳方案是将士兵组成
3
3 个特别行动队：第一队包含士兵
1
1 和士兵
2
2，第二队包含士兵
3
3，第三队包含士兵
4
4。特别行动队的初始战斗力分别为
4,
4,
3,
3,
4
4，修正后的战斗力分别为
4,
4,
1,
1,
4
4。修正后的战斗力和为
9
9，没有其它方案能使修正后的战斗力和更大。
输入
输入由三行组成。
第一行包含一个整数
n
n，表示士兵的总数。
第二行包含三个整数
a, b, c
a,b,c，经验公式中各项的系数。
第三行包含
n
n 个用空格分隔的整数
x_1,
x1
,
x_2,
x2
,
\dots,
…,
x_n
x
n
，分别表示编号为
1,
1,
2,
2,
\dots,
…,
n
n 的士兵的初始战斗力。
输出
输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。
样例输入
4
-1 10 -20
2 2 3 4
样例输出
9
提示
数据范围与提示
20\%
20% 的数据中，
n \le 1000
n≤1000；
50\%
50% 的数据中，
n \le 10^4
n≤104；
100\%
100% 的数据中，
1 \le n \le 10^6,\ –5 \le a \le –1,\ |b|,|c| \le 10^7,\ 1 \le x_i \le 100
1≤n≤106, –5≤a≤–1, ∣b∣,∣c∣≤107, 1≤xi
≤100。
来源/分类
ybttg DP 斜率优化