Problem25510--石子合并

25510: 石子合并

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

 

问题描述:

      在一个建筑工地上有许多堆石子,为了建筑的需要,要把所有的石子合成一堆。

      每一次合并,可以把两堆石子合并到一起,得到新的一堆石子,新堆石子的重量等于原来两堆石子的重量的和,合并这两堆石子消耗的体力等于原来两堆石子的重量之和。可以看出,所有的石子经过n-1次合并之后,就只剩下一堆了。在合并石子时总共消耗的体力等于每次合并所耗体力的和。

      假定已知每堆石子的重量,你的任务是设计出合并的次序方案,使合并石子时耗费的体力最少,输出这个最小的体力耗费值。

      例如有3堆石子,每堆石子的重量依次为285。可以先将13堆合并,新堆的重量为7,耗费体力为7。接着,将新堆与原先的第二堆合并,又得到新的堆,重量为15,耗费体力为15。所以总共耗费体力=7+15=22。可以证明22为最小的体力耗费值。

数据输入:

      从文件shizi.in中读入数据,文件中包括两行,第一行是一个整数n(1<n<=10000),表示原来石子的堆数。第二行包含n个整数,用空格分隔,第i个整数ai(1<ai<=20000)是第i堆石子的重量。

数据输出:

      结果输出到文件shizi.out中,只有一个整数,表示最小的体力耗费值。输入数据保证这个值小于231

输入输出样例:

shizi.in

3
2  8  5

shizi.out

22

说明:

对于30%的数据,保证有n<=1000
对于50%的数据,保证有n<=5000
对于全部的数据,保证有n<=10000

Source/Category