読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #336 Div.2 D / Div.1 B - Zuma

問題

Codeforces Round #336 Div.2 D / Div.1 B - Zuma
長さNの数列cが与えられる。cから回文となっている部分列を除去する操作を行ったとき、最小何回の操作で全て数を除去できるか?

制約

 1 \le N \le 500 \\
1 \le c_{i} \le N, \forall i \in [1, N]

解法

c[i] = c[m]となるところがあるとき、iからmを除去するときにかかる操作回数は、i+1からm-1を除去するときにかかる操作回数に等しい。(ただし、i=mもしくはi=m+1のときは、操作回数は1回)
よって、以下のDP(区間DP)で解ける。
 i > j のとき  dp[i][j] = 0
 c[i]=c[m], m \in [i,j]のとき  dp[i][j] = \min(dp[i][j], \max(1, dp[i+1][m-1]) + dp[m+1][j])
 c[i] \ne c[m], m \in [i,j] のとき  dp[i][j] = \min(dp[i][j], dp[i][m] + dp[m+1][j])
注意: m=jのとき、dp[m+1][j]は0である
答えは dp[1][N]
区間DPの書き方が分からない場合は蟻本pp.121-123(Bribe and Prisoners)を読もう!

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

計算量

i, jの取り方に O(N^2)、dpの更新( m \in [i, j])に O(N)なので、 O(N^3)

コード

上記では1-indexだが、コードは0-indexなので注意

感想

  • 区間DPを思いつかなかった
    • 確かに区間に対する操作だしね...
    • ある区間で最小だったら、それを使ってより大きい区間でも最小を求められるということが重要そう?