AT_dp_n Slimes

题目描述

有 $N$ 只史莱姆排成一行。最初，从左到右第 $i$ 只史莱姆的大小为 $a_i$。

太郎君想要将所有史莱姆合成为一只。他会不断重复以下操作，直到只剩下一只史莱姆：

• 选择左右相邻的两只史莱姆，将它们合成为一只新的史莱姆。合成前两只史莱姆的大小分别为 $x$ 和 $y$，合成后的史莱姆大小为 $x + y$。此时，太郎君需要支付 $x + y$ 的代价。合成前后，史莱姆们的相对位置不会发生变化。

请你求出太郎君需要支付的总代价的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出太郎君需要支付的总代价的最小值。

输入输出样例 #1

输入 #1

4
10 20 30 40

输出 #1

190

输入输出样例 #2

输入 #2

5
10 10 10 10 10

输出 #2

120

输入输出样例 #3

输入 #3

3
1000000000 1000000000 1000000000

输出 #3

5000000000

输入输出样例 #4

输入 #4

6
7 6 8 6 1 1

输出 #4

68

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 400$
• $1 \leq a_i \leq 10^9$

样例解释 1

可以按如下方式进行操作。用粗体表示正在合成的史莱姆。

• (10, 20, 30, 40) → (30, 30, 40)
• (30, 30, 40) → (60, 40)
• (60, 40) → (100)

样例解释 2

例如，可以按如下方式进行操作：

• (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

答案可能无法用 32 位整数型表示。

样例解释 4

例如，可以按如下方式进行操作：

• (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)

由 ChatGPT 4.1 翻译