Extra
Time
石子归并 Time:0.9s Memory:50M AC:0% Submit:8

设有N堆沙子排成一排,其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆(每次合并花费的代价为当前两堆沙子的总数量),这样经过N-1次归并后成为一堆,归并的总代价为每次合并花费的代价和。找出一种合理的归并方法,使总的代价最小。

例如:有3堆沙子,数量分别为13,7,8,有两种合并方案,

第一种方案:先合并1,2号堆,合并后的新堆沙子数量为20,本次合并代价为20,再拿新堆与第3堆沙子合并,合并后的沙子数量为28,本次合并代价为28,将3堆沙子合并到一起的总代价为第一次合并代价20加上第二次合并代价28,即48;

第二种方案:先合并2,3号堆,合并后的新堆沙子数量为15,本次合并代价为15,再拿新堆与第1堆沙子合并,合并后的沙子数量为28,本次合并代价为28,将3堆沙子合并到一起的总代价为第一次合并代价15加上第二次合并代价28,即43;

采用第二种方案可取得最小总代价,值为43。

【输入格式】

输入由若干行组成,第一行有一个整数,n(1≤n≤100);表示沙子堆数。第2至n+1行是每堆沙子的数量。 

【输出格式】

一个整数,归并的最小代价。

【输入样例】

输入文件名:shizi.in

7
13
7
8
16
21
4
18

【输出样例】

输出文件名:shizi.out

239