Codeforces 607B Zuma

Posted by

题目链接

http://codeforces.com/problemset/problem/607/B

题意

给出一个数字串,每次从中删去一个回文子串,问删完这个串最少要多少次

题解

裸的区间DP:设\(a[1\ldots n] \)表示原串,\(f[i][j] \)为删完区间\([i,j] \)所需要的最少次数。

状态转移方程:
\[ f[i][j]=\begin{cases}
f[i+1][j-1],\quad a[i]=a[j],\quad j-i+1>2 \\
min\{ f[i][k]+f[j][k]\} ,\quad a[i]\neq a[j],\quad i\leq k\leq j
\end{cases} \]

边界条件:当\(i=j\)或者\(a[i]=a[i+1] \)时,\(f[i][j]=1 \)。

显然答案为\(f[1][n] \)。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注