A29750.合并果子【队列】

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一个果园里,由n堆苹果。多多决定把所有的苹果合成堆。每一次合并,多多可以把两堆苹果合并到一起,消耗的体力等于两堆苹果的重量之和。可以看出,所有的苹果经过 n-1次合并之后,就只剩下一堆了。多多在合并苹果时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家,所以多多在合并果时要尽可能地节省体力。假定每个苹果重量都为1,并且已知有n堆苹果以及每堆苹果的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,输出这个最小的体力耗费值。

输入格式

两行,第一个代表有n个果子

n个数,代表一堆苹果的数量

输出格式

最小的体力耗费值。

输入输出样例

  • 输入#1

    4
    1 2 9 6

    输出#1

    30

说明/提示

0 <n <10000

首页