A5054. 史莱姆
编程题
普及/提高-
知识点
题目描述
有 $N$ 个史莱姆排成一排。最初，第 $i$ 个史莱姆的大小是 $a_i$ 。
太郎正试图将所有的史莱姆组合成一个更大的史莱姆。他会反复执行下面的操作，直到只有一个史莱姆为止：
- 选择两个相邻的史莱姆，将它们组合成一个新史莱姆。新史莱姆的大小为 $x + y$ ，其中 $x$ 和 $y$ 是组合前史莱姆的大小。这里需要花费 $x + y$ 。在组合史莱姆时，史莱姆的位置关系不会改变。
求可能产生的最小总成本。
#### 限制因素
- 所有输入值均为整数。
- $2 \leq N \leq 400$
- $1 \leq a_i \leq 10^9$
太郎正试图将所有的史莱姆组合成一个更大的史莱姆。他会反复执行下面的操作，直到只有一个史莱姆为止：
- 选择两个相邻的史莱姆，将它们组合成一个新史莱姆。新史莱姆的大小为 $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$
$N$
$a_1$ $a_2$ $\ldots$ $a_N$
输出格式
打印可能产生的最低总成本。
输入输出样例
输入 #1
4 10 20 30 40
输出 #1
190
输入 #2
5 10 10 10 10 10
输出 #2
120
输入 #3
3 1000000000 1000000000 1000000000
输出 #3
5000000000
说明/提示
### 样本 1 解释
太郎应该做的事情如下（粗体字显示的是正在组合的粘液）：
- (**10**, **20**, 30, 40) → (**30**, 30, 40)
- (**30**, **30**, 40) → (**60**, 40)
- (**60**, **40**) → (**100**)
太郎应该做的事情如下（粗体字显示的是正在组合的粘液）：
- (**10**, **20**, 30, 40) → (**30**, 30, 40)
- (**30**, **30**, 40) → (**60**, 40)
- (**60**, **40**) → (**100**)