ABC334C - Socks 2

ripity

なくしていない靴下を色の昇順に$${B=(B_1, \cdots, B_M)}$$とします。特に、$${M=2N-K}$$です。

DP をします。$${dp[i][j]:=}$$「$${(B_1, \cdots, B_{i-1})}$$からちょうど$${j}$$個を削除したときの、奇妙さの最小値」とします。求めるべき値は、$${M}$$が偶数のとき$${dp[M][0]}$$、$${M}$$が奇数のときは$${\min(dp[M-1][0], dp[M][1])}$$です。

遷移を考えます。考えるべきは次の 3 パターンです。

  • $${B_i, B_{i+1}}$$をペアにする。$${B_{i+2}}$$をペアに含むことを確定させる。$${j}$$は変化しない。

  • $${B_i, B_{i+1}}$$をペアにする。$${B_{i+2}}$$をペアに含まないことを確定させ、$${B_{i+3}}$$をペアに含むことを確定させる。$${j}$$は 1 増える。

  • $${B_i, B_{i+2}}$$をペアにする。$${B_{i+1}}$$をペアに含まないことを確定させ、$${B_{i+3}}$$をペアに含むことを確定させる。$${j}$$は 1 増える。

これを漸化式に落とし込めば良いです。$${O(N)}$$時間で解けることが確認できます。


この記事が気に入ったらサポートをしてみませんか？