Rockdu's Blog

Input输入字符串S(S的长度<= 5000)。Output输出最少的划分数量。Sample Input

abbaabaa

Sample Output

3​

首先我们看见回文串问题可以模仿Manacher向空隙中填满'#'符号。然后可以推知DP转移方程dp[i + j] = min(dp[i + j], dp[i - j - 1] + 1) {0<=i<=len - 1, 0<=j<=min(i, n - i - 1), s[i + j] == s[i - j]} 然后就可以轻松以比较小的常数的O(N^2)过掉。AC code:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 5e3 + 5;
int dp[maxn << 1], cnt;
char s[maxn << 1], r[maxn << 1];
int main() {
	memset(dp, 0x3f, sizeof(dp));
	gets(r);
	s[cnt++] = '#', dp[0] = 0;
	int len = strlen(r);
	for(register int i = 0; i < len; ++i)
		s[cnt++] = r[i], s[cnt++] = '#';
	for(int i = 1; i < cnt; ++i) {
		int a = min(cnt - i - 1, i);
		for(register int j = 0; j <= a && s[i - j] == s[i + j]; ++j)
			dp[i + j] = min(dp[i + j], dp[i - j - 1] + 1);
	}
	printf("%d", dp[cnt - 2]);
	return 0;
}