4259 - 动态规划:区间动态-直线
时间限制 : 1 秒
内存限制 : 128 MB
在操场上沿一直线排列着n堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数计为该次合并的得分。 我们希望这n-1次合并后得到的得分总和最小。
输入
第一行有一个正整数n（n<=300)，表示石子的堆数； 第二行有n个正整数，表示每一堆石子的石子数，每两个数之间用一个空格隔开。它们都不大于10000。
输出
一行，一个整数，表示答案。
样例
输入
3 1 2 9
输出
15