Slimes

题意翻译

有 $n$ 个数，第 $i$ 个数是 $a_i$ ，现在要进行 $n-1$ 次操作。对于每一次操作，可以把相邻两个数合并起来，并写上他们的和，这次操作的代价就是这个和。求代价最小值。

题目描述

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_n $ N $ 匹のスライムが横一列に並んでいます。最初、左から $ i $ 番目のスライムの大きさは $ a_i $ です。太郎君は、すべてのスライムを合体させて $ 1 $ 匹のスライムにしようとしています。スライムが $ 1 $ 匹になるまで、太郎君は次の操作を繰り返し行います。 - 左右に隣り合う $ 2 $ 匹のスライムを選び、それらを合体させて新しい $ 1 $ 匹のスライムにする。合体前の $ 2 $ 匹のスライムの大きさを $ x $ および $ y $ とすると、合体後のスライムの大きさは $ x\ +\ y $ となる。このとき、太郎君は $ x\ +\ y $ のコストを支払う。なお、合体の前後でスライムたちの位置関係は変わらない。太郎君が支払うコストの総和の最小値を求めてください。

输入输出格式

输入格式

入力は以下の形式で標準入力から与えられる。 > $ 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

输入样例 #4

6
7 6 8 6 1 1

输出样例 #4

说明

### 制約 - 入力はすべて整数である。 - $ 2\ \leq\ N\ \leq\ 400 $ - $ 1\ \leq\ a_i\ \leq\ 10^9 $ ### Sample Explanation 1 次のように操作を行えばよいです。操作対象のスライムを太字で表しています。 - (\*\*10\*\*, \*\*20\*\*, 30, 40) → (\*\*30\*\*, 30, 40) - (\*\*30\*\*, \*\*30\*\*, 40) → (\*\*60\*\*, 40) - (\*\*60\*\*, \*\*40\*\*) → (\*\*100\*\*) ### Sample Explanation 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\*\*) ### Sample Explanation 3 答えは 32-bit 整数型に収まらない場合があります。 ### Sample Explanation 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\*\*)