Home => ProblemSet => 2.12-51:石子合并III
Problem1714--2.12-51:石子合并III

1714: 2.12-51:石子合并III

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

在一个操场上摆放着一排 N 堆石子。现要将石子有次序地合并成一堆。规定每次只能选任意的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将 N 堆石子合并成一堆的最小得分。

Input

第一行一个整数 N。
接下来 一 行N个整数 ai，代表第 i 堆石子的石子数。

Output

输出将所有石子合并为一堆的最小得分。

Sample Input Copy 

3
3 4 3

Sample Output Copy 

16

HINT



1 <= n <= 10000

Source/Category

算法 贪心 动态规划 区间 
[ Submit ] [ Status ]