Codeforces Round #336 Div.2 D / Div.1 B - Zuma
問題
Codeforces Round #336 Div.2 D / Div.1 B - Zuma
長さNの数列cが与えられる。cから回文となっている部分列を除去する操作を行ったとき、最小何回の操作で全て数を除去できるか?
制約
解法
c[i] = c[m]となるところがあるとき、iからmを除去するときにかかる操作回数は、i+1からm-1を除去するときにかかる操作回数に等しい。(ただし、i=mもしくはi=m+1のときは、操作回数は1回)
よって、以下のDP(区間DP)で解ける。
のとき
のとき
のとき
注意: m=jのとき、dp[m+1][j]は0である
答えは
区間DPの書き方が分からない場合は蟻本pp.121-123(Bribe and Prisoners)を読もう!
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
計算量
i, jの取り方に、dpの更新()になので、
コード
上記では1-indexだが、コードは0-indexなので注意
感想
- 区間DPを思いつかなかった
- 確かに区間に対する操作だしね...
- ある区間で最小だったら、それを使ってより大きい区間でも最小を求められるということが重要そう?