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)を読もう！