B - RGB Matching Editorial by snuke
dp解法「何匹かの犬を白に変え、同じ色どうしでマッチさせたとき、白のペアのみ \(a\) の差のコストがかかる」と言い換える。
- R,G,B:それぞれ偶数匹ずつでなければならない。コストは 0 。
- 白:白どうしのペアは \(a\) の昇順に 2 つずつマッチさせていくのが最適。つまり、奇数番目の白は \(-a_i\)、偶数番目の白は \(a_i\) のコストがかかると思えば良い。
白に変えるかどうかを \(a\) の昇順に決めていく dp ができる。
- dp[何匹目まで決めたか][Rの偶奇][Gの偶奇][Bの偶奇][白の偶奇] = 最小コスト
実装上は偶奇系のを2進数でまとめる。
writer解説の RB
BG
を独立に計算しても良いという考察が思いつかなかったのでこうなりました。実装も楽。
posted:
last update: