最小中间和

2013年11月21日1,3980

题目描述

给定一个正整数序列a1,a2,…,an,不改变序列中的每个元素在序列中的位置,把它们相加,并用括号记每次加法所得的和,称为中间和。
编程:找到一种方法,添上n-1对括号,加法运算依括号顺序进行,得到n-2个中间和,使得求出使中间和最少。
例如给出的序列是4,1,2,3。
第一种添加括号方法:
((4+1)+(2+3))=((5)+(5))=(10),有三个中间和是5,5,10,它们之和为5+5+10=20;
第二种添括号方法:
(4+((1+2)+3))=(4+((3)+3)=(4+(6))=(10),中间和是3,6,10,它们之和为19。

输入

第一行为N,第二行依次为a1,a2,…,an(均为不大于1000的整数)。

输出

输出仅有一行为S(最小的中间和)。

样例输入

5 10 3 5 6 8

样例输出

72

代码