Codeforces 607B – Zuma

题目链接:Codeforces 607B

区间DP。$f(i, j)$表示区间$[i,j]$最少要消去多少次。

考虑最左边的点$i$,要么被单独删掉,要么和后面的组成回文。当$i$被单独删掉时,$f(i,j) = f(i + 1, j) + 1$。

$i$和后面的串组成回文的情况可以枚举和$c_i$相同的$c_k(i < k \leq j)$,我们可以这样分组$i, (i + 1, \cdots, k – 1), k, (k + 1, \cdots, j) $,显然$[k + 1, r]$这个区间对$f(i,j)$的贡献是$f(k+1, j)$,那么$[i+1, k -1]$对$f(i,j)$的贡献是$f(i+1, k -1)$。考虑$[i+1,k-1]$中最后一组被删掉的数字,如果是多个(以及是回文),那么一定与$i$和$k$构成回文;如果是一个,则也与$i$和$k$构成回文,所以最后一次删除可以将$i$和$k$一起删除。此时$f(i,j) = \min \{ f(i + 1, k – 1) + f(k – 1, j) \}, i < k \leq j, c_i = c_k $。有一种特殊情况是$c_i = c_{i + 1}$的时候$f(i,j) = f(i + 2) +1$。

综合以上三种情况,比出最小值:

$$f(i,j) = \min  \left  \{ \begin{aligned} & f(i + 1, j) + 1 \\ & f(i + 2, j) + 1 , (c_i = c_{i + 1}) \\ & \min_{c_i = c_k} \{ f(i + 1, k – 1) + f(k – 1, j) \} \end{aligned} \right .  $$

注意边界情况

$$f(i,j) =  \left  \{ \begin{aligned} & 0, & i > j \\ &1 , & i = j  \end{aligned} \right .  $$

 

 

说点什么

avatar
50
  Subscribe  
提醒