AT_dp_n Slimes

[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

N/A

### 制約 - 入力はすべて整数である。 - $ 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\*\*)