J18 例题-1 直线石子合并问题

题目描述

有 $N$ 堆石子排成一排，每堆石子有一定的数量。 现要将 $N$ 堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过 $N-1$ 次合并后成为一堆。 求出总的代价最小值。

输入格式

有多组测试数据，输入到文件结束。 每组测试数据第一行有一个整数 $n$ ，表示有 $n$ 堆石子。 接下来的一行有 $n$ 个数，分别表示这 $n$ 堆石子的数目，数字之间用空格隔开。

输出格式

若干行： 对于每组数据，输出一行，表示总代价的最小值。

样例输入

3
1 2 3
7
13 7 8 16 21 4 18

样例输出

9
239

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$0 < n \leq 200,0<a_i \leq 500$。