Problem1019--堆石子

1019: 堆石子

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2337  Solved: 582
[Submit] [Status] [Web Board] [Creator:]

Description

在一片沙滩上摆放着 n堆石子。 现要将石子有次序地合并成一堆。 规定每次选2 堆相邻石子合并成新的一堆，合并的费用为新的一堆石子数。试设计一个算法，计算出将 n堆石子合并成一堆的最小总费用。

Input

多组数据
输入数据第1行有1个正整数 n（1≤n≤300），表示有 n堆石子，每次选2堆石子合并。第2行有 n个整数， 分别表示每堆石子的个数（每堆石子的取值范围为[1,1000]） 。

Output

数据输出为一行， 表示对应输入的最小总费用。

Sample Input 

7
45 13 12 16 9 5 22

Sample Output 

313

Source/Category

2016年中南大学研究生复试机试题  
[Submit] [Status]