ここではゲーム・確率DPについて、学習していきます。

まずはじめに、以下の問題を見てみましょう。

問題

N 個のセグメントに分かれた 1 次元のケーキがあり、i (1 ≦ i ≦ N) 番目のセグメントには A_i 個のイチゴが載っています。これらのセグメントの中から切れ目を 1 つ選び、2 つのケーキに分けます。2 つのケーキに乗っているイチゴの数の差の最小値を求めてください。

(制約) 2 ≦ N ≦ 1000, 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ N)


この問題を解いてみましょう。切れ目は全部で N - 1 個しかないので全部試しに切ってみることを考えます。

ここで、例として、7 個のセグメントに左からイチゴが、8 個、12 個、13 個、7 個、2 個、17 個、6 個載っている状況を考えます。このケーキを 4 番目のセグメントと 5 番目のセグメントで切ってみると以下のようになります。



左側のケーキは 8 + 12 + 13 + 7 = 40 個、右側のケーキは 2 + 17 + 6 = 25 個イチゴが載っているので、差は |40 - 25| = 15 個と計算が出来ます。

このように、それぞれのケーキに載っているイチゴの数は足し算で計算が出来ることがわかりました。では、実際にやってみましょう。以下に問題を再掲します。

(問題)

N 個のセグメントに分かれた 1 次元のケーキがあり、i (1 ≦ i ≦ N) 番目のセグメントには A_i 個のイチゴが載っています。これらのセグメントの中から切れ目を 1 つ選び、2 つのケーキに分けます。2 つのケーキに乗っているイチゴの数の差の最小値を求めてください。