首页 > 代码库 > UVa 11584 Partitioning by Palindromes
UVa 11584 Partitioning by Palindromes
题意：
给出一个字符串，求最少能划分成多少个回文子串。
分析：
d[i] = min{d[j] + 1 | s[j+1]...s[i]是回文串}
d[i]表示前 i 个字符最少能分割的回文子串的个数
字符串从s[1]开始，边界d[0] = 0;
预处理：用从中间想两边拓展的方法，用flag[i][j]表示s[j]...s[i]是否是回文串
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1000 + 10; 8 bool flag[maxn][maxn]; 9 char s[maxn];10 int d[maxn];11 12 int main(void)13 {14 #ifdef LOCAL15 freopen("11584in.txt", "r", stdin);16 #endif17 18 int T;19 scanf("%d", &T);20 while(T--)21 {22 scanf("%s", s+1);23 memset(flag, false, sizeof(flag));24 int n = strlen(s+1); //n++;25 for(int i = 1; i <= n; ++i)26 {27 for(int j = 0; i-j>0 && i+j<=n && s[i-j]==s[i+j]; ++j)28 flag[i-j][i+j] = true;29 }30 for(int i = 1; i < n; ++i)31 {32 if(s[i] == s[i+1])33 {34 for(int j = 0; i-j>0 && i+j+1<=n && s[i-j]==s[i+j+1]; ++j)35 flag[i-j][i+j+1] = true;36 }37 }38 d[0] = 0;39 for(int i = 1; i <= n; ++i)40 {41 d[i] = d[i-1] + 1;42 for(int j = 0; j < i; ++j) if(flag[j+1][i]) 43 d[i] = min(d[i], d[j] + 1);44 }45 printf("%d\n", d[n]);46 }47 48 return 0;49 }
UVa 11584 Partitioning by Palindromes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。