20. 石子合并

【题目描述】

设有 $N$ 堆石子排成一排，其编号为 $1,2,3,…,N(N \leq 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$；

采用第二种方案可获得最小总代价。

【输入格式】

输入由若干行组成，第一行有一个整数，$n（1≤n≤100）$；表示石子堆数。第 $2$ 至 $n+1$ 行是每堆石子的重量。

【输出格式】

一个整数，表示合并的最小代价。

【样例输入】

7
13
7
8
16
21
4
18

【样例输出】

239

【提示】

合并总代价不大于 $2.1*10^8$.

【来源】

NOI 1995