首页 > 代码库 > Uva 11584，划分成回文串
Uva 11584，划分成回文串
题目链接：https://uva.onlinejudge.org/external/115/11584.pdf
题意：
一个字符串，将它划分一下，使得每个串都是回文串，求最少的回文串个数。
分析：
d(i)到第 i 个字符时的最优解（即最少划分为几个回文串），就有方程 d(i) = min(d(j)) + 1;(其中s[j+1,i]要是回文串)。
这样一来，枚举就是O(n^2)的复杂度，如果按照普通的判断s[j+1,i]是否是回文串，时间复杂度为O(n^3);先用O(n^2)的复杂度预处理is_huiwen[i][j]判断是否是回文串。前面我采用的DP的方案。这里学了一个更好写的方案，——中心扩展法。
这里值得注意的是： 预留一个dp[0] = 0;这样在当前面没有回文串时，而整个字符串是回文串的时候，就有d[i] = d[0]+1 =1;
#include <bits/stdc++.h>using namespace std;const int maxn = 1000+5;int n,kase,p[maxn][maxn],d[maxn];bool vis[maxn][maxn];char s[maxn];int is_palindrome(int i, int j){ if(i >= j) return 1; if(s[i] != s[j]) return 0; if(vis[i][j] == true) return p[i][j]; vis[i][j] = true; p[i][j] = is_palindrome(i+1, j-1); return p[i][j];}int main(){ int T; scanf("%d",&T); for(kase = 1; kase<=T; kase++) { memset(vis,0,sizeof(vis)); scanf("%s",s+1); n = strlen(s+1); d[0] = 0; is_palindrome(1,n); for(int i=1; i<=n; i++) { d[i] = i+1; for(int j=0; j<i; j++) { if(is_palindrome(j+1,i)) d[i] = min(d[i],d[j]+1); } } printf("%d\n",d[n]); } return 0;}
Uva 11584，划分成回文串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。