分数: 100 点
问题陈述
有 N 史莱姆排成一排。 最初, i从左边算起第一个史莱姆的大小为 a_i.
太郎正在尝试将所有史莱姆合并成一个更大的史莱姆。 他会重复执行以下操作,直到只剩下一个史莱姆:
- 选择两个相邻的史莱姆,并将它们组合成一个新的史莱姆。新史莱姆的大小为 x + y,其中 x 和 y 是组合之前史莱姆的大小。这里,成本为 x + y 开始。组合史莱姆时,史莱姆的位置关系不会改变。
找出可能产生的最小总成本。
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 400
- 1 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
打印可能产生的最小总成本。
示例输入 1
4 10 20 30 40
示例输出 1
190
太郎应该执行以下操作(合并的史莱姆以粗体显示):
- (10, 20, 30, 40) → (30, 30, 40)
- (30, 30, 40) → (60, 40)
- (60, 40) → (100)
示例输入 2
5 10 10 10 10 10
示例输出 2
120
太郎应该这样做,例如,如下:
- (10, 10, 10, 10, 10) → (20, 10, 10, 10)
- (20, 10, 10, 10) → (20, 20, 10)
- (20, 20, 10) → (20, 30)
- (20, 30) → (50)
示例输入 3
3 1000000000 1000000000 1000000000
示例输出 3
5000000000
答案可能不适合 32 位整数类型。
示例输入 4
6 7 6 8 6 1 1
示例输出 4
68
太郎应该这样做,例如,如下:
- (7, 6, 8, 6, 1, 1) → (7, 6, 8, 6, 2)
- (7, 6, 8, 6, 2) → (7, 6, 8, 8)
- (7, 6, 8, 8) → (13, 8, 8)
- (13, 8, 8) → (13, 16)
- (13, 16) → (29)