当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6792:Lady Layton and Stone Game

题目描述
Katori has many piles of stones, where there are $a_i$ piles containing exactly $i$ stones for $i = 1, 2, \ldots, n$.

Now, she wants to collect all these piles into one pile by merging one or more times. Each time she can pick $k$ $(L \leq k \leq 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 $T$ $(1 \leq T \leq 10)$, denoting the number of test cases. Then follow all the test cases.

For each test case, the first line contains three integers $n$, $L$ and $R$ $(1 \leq n \leq 10^5, 2 \leq L \leq R \leq \sum_{i = 1}^{n}{a_i})$, 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 $n$ integers, where the $i$-th integer is $a_i$ $(1 \leq a_i \leq 10^5)$, the number of piles containing exactly $i$ stones at the beginning.
输出解释
For each test case, output in one line $-1$ if it is impossible for her to achieve the task, or otherwise the minimum total cost to finish that.
输入样例
4
1 2 2
2
3 2 2
1 1 1
3 2 3
1 1 1
4 3 3
1 1 1 1
输出样例
2
9
6
-1
提示
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.
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6792

最后修改于 2020-10-25T23:34:25+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/2000MS(Java/Others) 524288/524288K(Java/Others)