题目描述
本题译自 JOI 2016 Final T1「オレンジの出荷」
JOI 社决定将收获的 N 个橙子分装进一些箱子内。在 JOI 社的工厂中,橙子排列在输送带上,依次编号为 1…N。橙子 i(1⩽i⩽N) 的大小为 Ai。由于分拣不方便,同一个箱子内,橙子的编号必须连续。
一个箱子内最多可以装 M 个橙子。在一个箱子内装一些橙子的成本为 K+s×(a−b)。K 是箱子本身的成本,所有箱子的成本一样。s 是该箱子中橙子的数目。a 是该箱子中最大橙子的大小,b 是该箱子中最小橙子的大小。
求包装这 N 个橙子所需的最小成本。
输入格式
第一行有三个整数 N,M,K,用空格分隔。
在接下来的 N 行中,第 i 行 (1⩽i⩽N) 有一个整数 Ai。
输入的所有数的含义见题目描述。
输出格式
输出一个整数,表示包装这 N 个橙子所需的最小成本。
样例 1
6 3 6
1
2
3
1
2
1
21
用两个箱子装。第一个箱子装橙子 1,2,3,第二个箱子装 4,5,6,总成本为 [6+3×(3−1)]+[6+3×(2−1)]=21。
16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19
164
用 11 个箱子装。这些箱子依次分别装了 1,3,1,1,3,1,1,2,1,1,1 个橙子,箱子 1 装了橙子 1,箱子 2 装了橙子 2,3,4,箱子 3 装了橙子 5,以此类推。
16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12
177
10 1 1000000000
1
1
1
1
1
1
1
1
1
1
10000000000
答案可能会爆 int 。
数据范围与提示
对于所有数据,1⩽N⩽2×104,1⩽M⩽1000,0⩽K⩽109,1⩽Ai⩽109(1⩽i⩽N),M⩽N。
Subtask # |
N |
M |
分值 |
1 |
N⩽20 |
M⩽1000 |
20 |
2 |
N⩽2000 |
M⩽100 |
50 |
3 |
N⩽2×104 |
M⩽1000 |
30 |