JOI 2010-2 お菓子の分割
https://joi2010ho.contest.atcoder.jp/tasks/joi2010ho_b
案外すっと解けたけど色々新しいことが体験できたので記す
問題の意味を変える
棒を切って渡すという感じだが、
このような問題とも読み取れる
どちらか受け取る人を決める
次切るまで、1ミリを受け取り続ける
切った時コストを払い、
またどちらか受け取る人を決める
なので
dp[i][j][k] := 次からkの人(0の時自分、1のとき相手)が受け取り、今i番目まで見て、自分がjミリ受け取っているとき最小のコスト
とすれば
1.そのまま受け取り続ける
//自分が受け取る dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0]); //相手が受け取る dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);
2.自分が受け取った後、切る
if (j > 0) { //切った後受け取る人を自分にする dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0] + t[i]); //切った後受け取る人を相手にする dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + t[i]); }
3.相手が受け取った後、切る
//切った後受け取る人を自分にする dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + t[i]); //切った後受け取る人を相手にする dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + t[i]);
これで解いた
ただ、iの部分をそのまま利用するとMLEしてしまう
しかし前回の記録にアクセスするのはi-1の分だけなので
最適化することができる
これでAC
