NECプログラミングコンテスト2021 (AtCoder Beginner Contest 229) F - Make Bipartite (500)
コンテスト中の考察
0と結んでいる線の2本の間の間隔が奇数の場合、それらが$ Bによって繋がってはいけない
0と連続した2頂点の3頂点を考えると、最低でも1本は消す必要がある
$ dp[i][j][k] で考える
iは最初の0との辺を消したか、jは今見ている頂点、kは今見ている頂点の0との辺を消したか
初期値は以下のとおり
$ dp[1][0][0] = A_0
$ dp[0][0][1] = A_1
$ dp[0][0][0] = B_0
$ dp[1][0][1] = A_0 + A_1
そこから3本の内一本が消えている条件が守られるように$ j \gt 0の場合も更新していく
最後については$ iの条件を満たすように更新する
奇数の場合に繋げてはいけない条件をDP内で考慮しておらずWA
ナイーブ解と比較した結果気付いた
解説の解法
頂点に色を持たせて考える
$ dp[i][j][k] で考える
iは1が0と同じ色か、jは今見ている頂点、kは今見ている頂点が0と同じ色か
そうすると考える初期値は
$ dp[0][0][0] = A_0
$ dp[1][0][1] = 0
遷移は直前と同じ色にするには$ B_iのコストがかかり、0と同じ色にするには$ A_iのコストがかかるというのを計算すれば良い
最後に$ iの条件によって$ B_{n-1}を消す必要がある場合はそのコストを加え、最小値が答え
順に見ていくだけなので$ \mathcal{O}(N)