J - 刺身

問題文

きつねのしえるは川で釣りをしていた．黒くて細長い魚を手に入れることができたので，その場で切り刻んで刺身にして食べることにした．

魚は体長が N センチメートルある．奇妙なことに，この魚は身体の部分ごとに密度が異なっていた． 魚の身体を頭から 1 センチメートルごとに区切って番号を 1, 2, ..., N と付けるとき，身体の i 番目の部分の重みは w_i であった． 魚の i 番目から j 番目までの部分を [i..j] と表すことにする． 最初，しえるは魚の身体 [0..N-1] を 1 枚だけ持っていると見なせる．しえるはこれを切っていき最終的に N 個に分割された魚の身体 [0..0], [1..1], ..., [N-1..N-1] を得たい．

しえるは今野外におり，まな板などを持っていないので，次のようなアクロバティックな方法で魚の身体を切っていくことにした ： まず，魚の身体を 1 枚取る．これを [i..j] とする．この魚の身体は長さが少なくとも 2 センチメートル以上でなければならない．すなわち， j-i ≥ 1 でなければならない．次に，それを空中に投げる．そして日本刀を手に持ち，宙に舞う魚を真っ二つに切る．このとき，しえるは強靭な運動神経によって任意の位置でこの魚を切ることができるが，必ず 1 センチメートル区切りの位置で切るものとする．これにより，元の魚の身体 [i..j] を，任意の切断位置 k (i ≤ k < j) によって，[i..k] と [k+1..j] の 2 つに分割するのである． このアクロバティックな方法で魚の身体を 2 つに切るとき，元の身体の重さ (=w_i+w_i+1+...+w_j) だけコストがかかる．

しえるは，魚のすべての部分を 1 センチメートル区切りに切るのにかかるコストの合計値を最小にしたい．

入力形式

入力は以下の形式で与えられる．

N
w1 w2 ... wN

N は魚の体長である．w_i は魚の i 番目の部分の重さである．

出力形式

魚を N 個に切り分けるのにかかるコストの合計の最小値を出力せよ．

制約

• 2 ≤ N ≤ 4,000
• 1 ≤ w_i ≤ 10¹⁰
• 入力値はすべて整数である．

この問題の判定には，3 点分のテストケースのグループが設定されている． このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• 1 ≤ N ≤ 100

入出力例

入力例 1

3
1 2 3

出力例 1

9

まず，魚全体を 2 番目と 3 番目の部分の間で切る．これには 1+2+3 = 6 のコストがかかる． 次に，1 番目と 2 番目の部分の間で切る．これには 1+2=3 のコストがかかる．合計で 6+3=9 のコストがかかり，これが最善手である．

入力例 2

6
9876543210 9876543210 9876543210 9876543210 9876543210 9876543210

出力例 2

158024691360

入力例 3

10
127 131 137 139 149 151 157 163 167 173

出力例 3

5016