4305: §2 9 【例9.18】合并石子
[Creator : ]
Description
在一个操场上一排地摆放着 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
计算出将 $N$ 堆石子合并成一堆的最小得分。
例如：$1\ 2\ 3\ 4$，有不少合并方法
计算出将 $N$ 堆石子合并成一堆的最小得分。
例如：$1\ 2\ 3\ 4$，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19) 1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24) 1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
Input
第一行为一个正整数$N\ (2≤Ｎ≤300)$；
第二行包括 $n$ 个正整数，第 $i$ 个整数 $a_i\ (1 \leq a_i \leq 10,000)$ 表示第 $i\ (1 \leq i \leq N)$ 堆石子的个数。
第二行包括 $n$ 个正整数，第 $i$ 个整数 $a_i\ (1 \leq a_i \leq 10,000)$ 表示第 $i\ (1 \leq i \leq N)$ 堆石子的个数。
Output
一个正整数，即最小得分。
Sample 1 Input
7
13 7 8 16 21 4 18
Sample 1 Output
239
Sample 2 Input
3
1 2 3
Sample 2 Output
9
Sample 3 Input
4
1 2 3 4
Sample 3 Output
19