“对于第 $i$ 披分发的成绩单”更正为“对于第 $i$ 批分发的成绩单”

$————————————————————$

[THUSC2016] 成绩单

题目描述

期末考试结束了，班主任 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

样例输入 #1

10
3 1
7 10 9 10 6 7 10 7 1 2

样例输出 #1

15

提示

$n \leq 50$，$a \leq 1500$，$b \leq 10$，$w_i \leq 1000$。