Preparing NOJ

最小代价树

1000ms 65536K

Description:

以下方法称为最小代价的字母树:给定一正整数序列,例如:4123,在不改变数的位置的条件下把它们相加,并且用括号来标记每一次加法所得到的和。
例如:((4+1+ 2+3))=((5+5))=10。除去原数不4123之外,其余都为中间结果,如5510,将中间结果相加,得到:5+5+10=20,那么数20称为此数列的一个代价,若得到另一种算法:(4+((1+2+3))=4+((3+3))=4+6))=10,数列的另一个代价为:3+6+10=19。若给出N个数,可加N-1对括号,求出此数列的最小代价。
注:结果范围不超出longint.

Input:

第一行为数N(1≤N≤200),第二行为N个正整数,整数之间用空格隔开。

Output:

输出仅一行,即为最少代价值。

Sample Input:

4
4  1  2  3

Sample Output:

19

Note:

本题由旧版NOJ导入,来源:OIBH 模拟赛

Info

NOJ

Provider NOJ

Code NOJ1038

Tags

Submitted 13

Passed 6

AC Rate 46.15%

Date 04/20/2019 10:03:10

Related

Nothing Yet