#AT14. Slimes
Slimes
[N] Slimes(dp_n)
来源: AtCoder Educational DP Contest - Problem N 原题时限:2 秒 / 内存:1024 MB
题目描述
有 只史莱姆排成一列。初始时,从左数第 只史莱姆的大小为 。
太郎想把所有史莱姆合并成一只更大的史莱姆。他会重复下面的操作,直到只剩下一只史莱姆:
- 选择两只相邻的史莱姆,把它们合并成一只新的史莱姆。若合并前两只史莱姆的大小分别为 和 ,则新史莱姆的大小为 ,并且需要支付代价 。合并过程中,史莱姆之间的相对位置顺序不改变。
求所需支付代价总和的最小值。
输入格式
输入由标准输入按以下格式给出:
N
a_1 a_2 \ldots a_N
输出格式
输出所需支付代价总和的最小值。
数据范围
- 输入中的所有值均为整数。
样例 1
输入:
4
10 20 30 40
输出:
190
样例 2
输入:
5
10 10 10 10 10
输出:
120
样例 3
输入:
3
1000000000 1000000000 1000000000
输出:
5000000000
样例 4
输入:
6
7 6 8 6 1 1
输出:
68