51nod-1154 回文串划分

1154 回文串划分  基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题  收藏  关注 有一个字符串S，求S最少可以被划分为多少个回文串。 例如：abbaabaa，有多种划分方式。 a|bb|aabaa - 3 个回文串 a|bb|a|aba|a - 5 个回文串 a|b|b|a|a|b|a|a - 8 个回文串 其中第1种划分方式的划分数量最少。 Input 输入字符串S(S的长度<= 5000)。 Output 输出最少的划分数量。 Input示例 abbaabaa Output示例 3

思路：dp,dp[i]表示为 前 i为 所划分的最小数量，则两种转移方程。

一：dp[i]=min{dp[i],dp[j]+1}    (j<i且 区间 [j+1->i]是回文串)

因此需要预处理出 以 s[j-i]是否为回文串，可以用Manacher算法处理

二：dp[j]=min{dp[j],dp[k-1]+1}  (这种是以 s[i]为中心，j,k关于i对称且a[j]==a[k] 。或者 a[j],a[k]为中心，a[j]==a[k].向两边扩展)

Code1:

#include<iostream> using namespace std; const int MAX_N=10005; string str; char str[MAX_N]; int n,len[MAX_N]; int dp[MAX_N]; int Manacher(char str[]); int main() { ios::sync_with_stdio(false); cin>>str; for(int i=0;i<str.size();++i) str[n++]='#',str[n++]=str[i]; str[n++]='#'; Manacher(str); for(int i=0;i<str.size();++i) dp[i]=i+1; for(int i=1;i<str.size();++i) if(len[i+1]-1==i+1) dp[i]=1; else{ for(int j=0;j<i;++j) if(len[i+j+2]-1>=i-j) dp[i]=min(dp[i],dp[j]+1); } cout<<dp[str.size()-1]<<endl; return 0; } int Manacher(char str[]) //代码长度优化 { int ans=1,p=0,l=0,r=0; int i; for(i=0;i<n&&r<n;++i) if(i<r&&len[2*p-i]<r-i) len[i]=len[2*p-i]; else{ if(i<r&&len[2*p-i]>=r-i){ l=2*i-r; p=i; }else p=l=r=i; while(l>=0&&r<n){ if(str[l]==str[r]){ l--; r++; }else break; } len[i]=r-p; ans=max(ans,len[i]); } while(i<n){ len[i]=(len[2*p-i]>r-i)?n-i:len[2*p-i]; i++; } return ans-1; }

Code2:

#include<iostream> using namespace std; const int MAX_N=5005; string str; int dp[MAX_N]; int main() { ios::sync_with_stdio(false); while(cin>>str) { int n=str.size(); for(int i=0;i<n;i++) dp[i]=i+1; for(int i=0;i<n;i++) { for(int j=i,k=i;j<n&&k>=0;j++,k--) if(str[j]==str[k]) dp[j]=min(dp[j],dp[k-1]+1); else break; for(int j=i,k=i+1;j<n&&k>=0;j++,k--) if(str[j]==str[k]) dp[j]=min(dp[j],dp[k-1]+1); else break; } cout<<dp[n-1]<<endl; } return 0; }