P7459 - Lady Layton and Stone Game

内存限制：128 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

Katori has many piles of stones, where there are

aipiles containing exactly

istones for

i=1,2,…,n.
Now, she wants to collect all these piles into one pile by merging one or more times. Each time she can pick

(L≤k≤R)piles and merge them into one, and the cost of that will be the number of stones in the new pile.
Can you help her find the best way to achieve that with the minimum possible total cost?

There are several test cases.
The first line contains an integer

(1≤T≤10), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains three integers

Land

(1≤n≤105,2≤L≤R≤∑ni=1ai), denoting the maximum number of stones in each piles at the beginning, the lower bound and the upper bound of the number of piles she can merge at once, respectively.
The second line contains

nintegers, where the

i-th integer is

(1≤ai≤105), the number of piles containing exactly

istones at the beginning.

For each test case, output in one line

−1if it is impossible for her to achieve the task, or otherwise the minimum total cost to finish that.


	
	
		For the first sample case, there are two piles [1, 1] at the beginning.
The best way is to merge [1, 1] into [2] directly, and the cost is 2.

For the second sample case, there are three piles [1, 2, 3] at the beginning.
The best way is to merge [1, 2] into [3] at first, and then merge [3, 3] into [6].
The minimum total cost is 3 + 6 = 9.

For the third sample case, there are three piles [1, 2, 3] at the beginning.
The best way is to merge [1, 2, 3] into [6] directly, and the cost is 6.

For the fourth sample case, there are four piles [1, 2, 3, 4] at the beginning.
Neither can she collect them into one pile directly nor by merging several times, so it is impossible for her to achieve the task.

2020 Multi-University Training Contest 3

7459: Lady Layton and Stone Game

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签