区间型DP【仅题目】

石子归并(merge)

【问题描述】

在一个操场按次序从左到右摆放着n堆石子(n≤100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分,求最小的得分总和。

【输入格式】

第一行为石子堆数n;

第二行为每堆的石子数,每两个数之间用一个空格分隔。

【输出格式】

最小的得分总和。

【输入样例】

6

3 4 6 5 4 2

【输出样例】

61

样例说明:

3 4 6 5 4 2

7 6 5 4 2

13 5 4 2

13 5 6

13 11

24

7+13+6+11+24=61

点赞