8633 回文划分
时间限制:1000MS 内存限制:1000K
题型: 编程题 语言: 无限制
Description
我们说一个字符串是回文串，那么意味着这个串从两边读起来的字母都是一样的。例如racecar是回文串，
然而fastcar则不是。
对一个串的划分意思是将一个串划分为若干个部分。例如，racecar可以划分为race 和car两部分。给出
一个串，要把这个串划分为若干个回文串，那么至少要把这个串划分为多少部分？
例如
'racecar'已经是回文串，划分为1 个部分即可（这个部分就是racecar）。
'fastcar' 需要被划分为七个部分 ('f', 'a', 's', 't', 'c', 'a', 'r')。根据回文串的定义，单个字母也是回文串。
'aaadbccb' 分成可以被分为三个回文串 ('aaa', 'd', 'bccb')。找不到更少的划分方法。
输入格式
输入的第一行是数字T，表示输入文件含有T个CASE。之后有T行，每行有一个长度不大于1000的字
符串，全部由小写字母组成，中间没有空格。
输出格式
对于每个CASE，输出一个数字，表示对该字符串的回文串最小划分。
输入样例
3
racecar
fastcar
aaadbccb
输出样例
1
7
3
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = ;
char s[N];
int dp[N]; int is_Palindrome(int l,int r) //判断字符串l~r的字符串是否是回文串
{
for(;l<r;l++,r--)
if(s[l]!=s[r])
return ;
return ;
} int main()
{
int T,len,i,j;
cin>>T;
while(T--){
cin>>s;
len=strlen(s);
memset(dp,-,sizeof(dp));
dp[]=;
for(i=;i<len;i++)
if(is_Palindrome(,i)) {
dp[i]=;
}
else {
for(j=;j<i;j++){
if(is_Palindrome(j+,i)){
if(dp[i]==-)
dp[i]=dp[j]+;
else
dp[i]=min(dp[i],dp[j]+);
}
} }
cout<<dp[len-]<<endl;
}
return ;
}