← 返回题目

题库练习史莱姆

← 上一题下一题 →

A5054 | $史莱姆$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有 $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

输入 #2

5
10 10 10 10 10

输出 #2

输入 #3

3
1000000000 1000000000 1000000000

输出 #3

5000000000

C++ 编辑器

输入

输出