#397. 石子合并
石子合并
石子合并
题目描述
有 堆石子排成一排,编号为 。每堆石子有一定的质量,使用一个整数表示。
现在要将这 堆石子全部合并成为一堆。每次只能选择相邻的两堆石子合并,合并的代价为这两堆石子的质量之和。合并后,新的一堆质量等于原来两堆质量之和,并与原先两堆的其他相邻石堆相邻。
由于合并顺序不同,总代价可能不同。请计算把所有石子合并成一堆所需的最小总代价。
例如,对于 四堆石子:
- 先合并 和 ,代价为 ,得到 ;再合并 和 ,代价为 ,最后合并 和 ,代价为 ,总代价为 。
- 如果第一步仍合并 和 ,得到 ;第二步合并 和 ,代价为 ,得到 ;最后合并两堆的代价为 ,总代价为 。
最小总代价为 。
输入格式
第一行一个整数 ,表示石子堆数。
第二行有 个整数,依次表示各堆石子的质量。
输出格式
输出一个整数,表示将所有石子合并为一堆的最小总代价。
数据范围
- 。
- 每堆石子的质量为正整数,且不超过 。
输入样例
4
1 3 5 2
输出样例
22
提示
只能合并当前相邻的两堆,不能任意挑选两堆合并。当 时,无需合并,答案为 。