2186: 宝典2第十一章合并魔法石1

【题目描述】合并魔法石１(merge1.cpp/c/pas)

太空梯的能量导轨上有n堆魔法石排成一排，其编号为1，2，3，…，n(n≤100)。每块魔法石有一定的数量，例如有7堆魔法石，分别为13，7，8，16，21，4，18。

现在要将n堆魔法石归并成为一堆。归并的过程为每次只能将相邻的两堆魔法石堆成一堆，这样经过n－1次归并后成为一堆，如上面的7堆魔法石，可以有多种方法归并成一堆，其中的两种方法如图所示。

则（a）的归并代价为20+24+25+44+69+87=267

（b）的归并代价为15+37+22+28+59+87=248

可见不同的过程得到的归并代价是不一样的，现在请编程找出一种合理的方法，使归并代价最小。

【输入格式】

第一行为一个整数n，且1<n≤100，表示有n堆沙子，第二行为n堆魔法石的数量。

【输出格式】

一个整数，即最小代价。

【输入样例1】

7

13 7 8 16 21 4 18

【输出样例1】

239

【输入样例2】

10

12  3  13  7  8  23  14  6  9  34

【输出样例2】

398