#AT14. Slimes

Slimes

[N] Slimes(dp_n)

来源: AtCoder Educational DP Contest - Problem N 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 只史莱姆排成一列。初始时,从左数第 ii 只史莱姆的大小为 aia_i。

太郎想把所有史莱姆合并成一只更大的史莱姆。他会重复下面的操作,直到只剩下一只史莱姆:

  • 选择两只相邻的史莱姆,把它们合并成一只新的史莱姆。若合并前两只史莱姆的大小分别为 xx 和 yy,则新史莱姆的大小为 x+yx + y,并且需要支付代价 x+yx + y。合并过程中,史莱姆之间的相对位置顺序不改变。

求所需支付代价总和的最小值。

输入格式

输入由标准输入按以下格式给出:

N
a_1 a_2 \ldots a_N

输出格式

输出所需支付代价总和的最小值。

数据范围

  • 输入中的所有值均为整数。
  • 2≤N≤4002 \le N \le 400
  • 1≤ai≤1091 \le a_i \le 10^9

样例 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