题解 CF607B 【Zuma】

查看原题请戳这里

题目大意：

从一个序列中每次取出一个回文串，剩余部分拼起来形成一个新的序列，问取几次能把这个序列取完。

---

这道题我们可以用区间DP的方法去解决。

若$a[1,n]$为题目给出的序列，用$f[i][j]$表示将区间$[i,j]$中的数取完需要的最少的次数，那么显然$f[i][i]=1$，且当$a[i]=a[j]$时$f[i][i+1]=1$，当$a[i] \neq a[i+1]$时$f[i][i+1]=2$。有用我们再后续进行动态规划时更新的最短的区间长度为$3$，所以$f[i][i]$和$f[i][i+1]$两种情况需要特殊处理。

在更新$f[i][j]$时，最简单的思路就是把$f[i][j]$分成$f[i][k]$和$f[k+1][j]$两部分进行处理（其中$k \in [i,j)$），即

$$f[i][j]=\min (f[i][j],f[i][k]+f[k+1][j]),k \in [i,j)$$

而对于$a[i]=a[j]$的情况，当区间$[i+1,j-1]$还剩最后一个可以一次取出的序列$b$时（显然$b$是回文的），我们可以将$a[i]$、$a[j]$和$b$组成一个新的回文串同时取出（即组成$a[i]\ b\ a[j]$），从而我们可知当$a[i]=a[j]$时，

$$f[i][j]=\min (f[i][j],f[i+1][j-1])$$

然后根据上述两式DP即可。

code:

cpp

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 1000000009
#define qwq printf("qwq\n");

using namespace std;

int read() {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,a[505],f[505][505];

int main() {
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) 
			f[i][j] = INF;
	for(int i = 1; i <= n; i++) f[i][i] = 1, f[i][i + 1] = 1;
	for(int i = 1; i < n; i++) if(a[i] != a[i + 1]) f[i][i + 1]++;
	for(int i = 3; i <= n; i++)
		for(int j = 1; j <= n - i + 1; j++) {
			int l = j, r = j + i - 1;
			if(a[l] == a[r]) f[l][r] = f[l + 1][r - 1];
			for(int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
		}
	printf("%d\n", f[1][n]);
    return 0;
}