#397. 石子合并

石子合并

石子合并

题目描述

有 NN 堆石子排成一排,编号为 1,2,…,N1,2,\ldots,N。每堆石子有一定的质量,使用一个整数表示。

现在要将这 NN 堆石子全部合并成为一堆。每次只能选择相邻的两堆石子合并,合并的代价为这两堆石子的质量之和。合并后,新的一堆质量等于原来两堆质量之和,并与原先两堆的其他相邻石堆相邻。

由于合并顺序不同,总代价可能不同。请计算把所有石子合并成一堆所需的最小总代价。

例如,对于 1 3 5 21\ 3\ 5\ 2 四堆石子:

  • 先合并 11 和 33,代价为 44,得到 4 5 24\ 5\ 2;再合并 44 和 55,代价为 99,最后合并 99 和 22,代价为 1111,总代价为 2424。
  • 如果第一步仍合并 11 和 33,得到 4 5 24\ 5\ 2;第二步合并 55 和 22,代价为 77,得到 4 74\ 7;最后合并两堆的代价为 1111,总代价为 4+7+11=224+7+11=22。

最小总代价为 2222。

输入格式

第一行一个整数 NN,表示石子堆数。

第二行有 NN 个整数,依次表示各堆石子的质量。

输出格式

输出一个整数,表示将所有石子合并为一堆的最小总代价。

数据范围

  • 1≤N≤3001\le N\le300。
  • 每堆石子的质量为正整数,且不超过 10001000。

输入样例

4
1 3 5 2

输出样例

22

提示

只能合并当前相邻的两堆,不能任意挑选两堆合并。当 N=1N=1 时,无需合并,答案为 00。