石子归并

成绩 0 开启时间 2013年01月15日 星期二 15:55
折扣 0.8 折扣时间 2013年01月15日 星期二 15:55
允许迟交 是 关闭时间 2013年01月15日 星期二 15:55
输入文件 shizi.in 输出文件 shizi.out

设有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