Home => ProblemSet => 2.12-50:石子合并II
Problem1713--2.12-50:石子合并II

1713: 2.12-50:石子合并II

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

Description

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

Input

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

Output

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

Sample Input Copy 

4
1 1 1 1

Sample Output Copy 

8

HINT

N≤40000,ai≤200

Source/Category

Garsia-Wac 算法 动态规划 区间 
[ Submit ] [ Status ]