UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3229. [Sdoi2008]石子合并

统计 下载数据

Description

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

Input

  第一行是一个数N
  以下N行每行一个数A,表示石子数目。
 

Output

  共一个数,即N堆石子合并成一堆的最小得分。

 

Sample Input

4
1
1
1
1

Sample Output

8

Hint

对于 100% 的数据,1≤N≤40000

对于 100% 的数据,1≤A≤200

Source