お菓子の分割 - yamake's blog

この問題で一生悩んで結局解説ACをしました。

全然わからなかったけど、理解してみると簡単だったので整理を兼ねて自分の解法を書きます。

まあ、DPですね（終了）。

分ける二人の名前をそれぞれ0, 1として大きさ1のお菓子をn/2個片方が取る、最後のお菓子の欠片を自分が取った時はコスト0、そうでないときは直前の割れ目のコストを加算して最小値を取ります。

dpテーブルは

$dp[i][j][k]:=i番目までのお菓子の欠片を見た時、j君がk個取るために必要なコストの最小値$

とします。

a[0]=0, a[1]~a[n-1] は入力の通りです。

分割時のコストは直前と取る人が違うときのみ発生するので、

dp遷移はi個目を見ていて0君がj個目を取りたいとき、min(0君が最後にとってj-1個取ったときのコスト、1君が最後にとって0君がj-1個取ったときのコスト+割るためのコスト)とすれば良いです。

dpテーブルの定義より後者は $dp[i-1][1][i-(j-1)]$ とすれば良いので、

$dp[i][0][k]=\min(dp[i-1][0][k-1],dp[i-1][1][i-(j-1)]+a[i-1])$

$dp[i][1][k]=\min(dp[i-1][1][k-1],dp[i-1][0][i-(j-1)]+a[i-1])$

となります。

dpテーブルを全部持つとMLEするので配列は使いまわしました。

答えは $\min(dp[n][0][n/2],dp[n][1][n/2])$ で、

計算量は $O(N^2)$ です。

（提出コードのurlが違っていたので修正しました。指摘してくれたRorentさん、ありがとうございますm(_ _)m）