2326. [THUSC 2016] 成绩单

你以为我有数据？
[UPD] 现在有了

【问题描述】

期末考试结束了，班主任 L 老师要将成绩单分发到每位同学手中。 L 老师共有$n$份成绩单，按照编号从$1$到$n$的顺序叠放在桌子上，其中编号为$i$的成绩单分数为$w_i$。

成绩单是按照批次发放的。发放成绩单时，L 老师会从当前的一叠成绩单中抽取连续的一段，让这些同学来领取自己的成绩单。当这批同学领取完毕后， L 老师再从剩余的成绩单中抽取连续的一段，供下一批同学领取。经过若干批次的领取后，成绩单将被全部发放到同学手中。

然而，分发成绩单是一件令人头痛的事情，一方面要照顾同学们的心理情绪，不能让分数相差太远的同学在同一批领取成绩单；另一方面要考虑时间成本，尽量减少领取成绩单的批次数。对于一个分发成绩单的方案，我们定义其代价为：

\[a \times k + b \times \sum_{i = 1}^{k}(max_i - min_i)^2\]

其中，$k$是方案中分发成绩单的批次数，对于第$i$批分发的成绩单，$max_i$是最高分数，$min_i$是最低分数。$a, b$是给定的评估参数。

现在，请你帮助 L 老师找到代价最小的分发成绩单的方案，并将这个最小的代价告诉 L 老师。当然，分发成绩单的批次数$k$是由你决定的。

【输入格式】

第一行包含一个正整数$n$，表示成绩单的数量。

第二行包含两个非负整数$a, b$，表示给定的评估参数。

第三行包含$n$个正整数$w_i$，表示第$i$张成绩单上的分数。

【输出格式】

仅一个正整数，表示最小的代价是多少。

【样例输入1】

10
5 1
1 2 6 10 8 6 6 4 2 2

【样例输出1】

24

【样例输入2】

9
10 3
5 8 9 5 8 6 10 5 1

【样例输出2】

56

【样例说明】

样例1的具体方案为：

第1批，分发$[10, 8]$，落差为$2$，剩余成绩单为$[1, 2, 6, 6, 6, 4, 2, 2]$；

第2批，分发$[6, 6, 6, 4]$，落差为$2$，剩余成绩单为$[1, 2, 2, 2]$；

第3批，分发$[1, 2, 2, 2]$，落差为$1$，分发完毕。

总代价为$3 \times 5 + (2^2 + 2^2 + 1^2) \times 1 = 24$。

样例2的具体方案为：

第1批，分发$[8, 9]$，落差为$1$，剩余成绩单为$[5, 5, 8, 6, 10, 5, 1]$；

第2批，分发$[8]$，落差为$0$，剩余成绩单为$[5, 5, 6, 10, 5, 1]$；

第3批，分发$[10]$，落差为$0$，剩余成绩单为$[5, 5, 6, 5, 1]$；

第4批，分发$[5, 5, 6, 5]$，落差为$1$，剩余成绩单为$[1]$；

第5批，分发$[1]$，落差为$0$，分发完毕。

总代价为$5 \times 10 + (1^2 + 0^2 + 0^2 + 1^2 + 0^2) \times 3 = 56$。

【数据规模与约定】

对于全部数据，满足$0 \leq a, b \leq 200$，$1 \leq w_i \leq 5000$。

单调序列：满足$w_1 \leq w_2 \leq \cdots \leq w_n$或$w_1 \geq w_2 \geq \cdots \geq w_n$。

单峰序列：存在$1 \leq i \leq n$，满足$w_1 \leq w_2 \leq \cdots \leq w_i$且$w_i \geq w_{i + 1} \geq \cdots \geq w_n$。

【来源】

THUSC2016第一题