首页 > 代码库 > UVa 11404 回文子序列（LCS求最长回文串长度）
UVa 11404 回文子序列（LCS求最长回文串长度）
https://vjudge.net/problem/UVA-11404
题意：
给定一个由小写字母组成的字符串，删除其中的0个或多个字符，使得剩下的字母（顺序不变）组成一个尽量长的回文串。如果有多解，输出字典序最小的解。
思路：
首先，最长回文子串的长度可以通过正序字符串和逆序字符串进行LCS得出。
但是这道题目麻烦的是还要输出这个回文串，并且字典序得最小。
应用的主要还是LCS的思想方法，不过在进行状态转移的时候，再加上字符串的状态转移。
不过最后得到的字符串不一定是回文串，但是它的前一半肯定是回文串的一半，那么后面的一半只需要根据前面的就可以得出。
http://blog.csdn.net/shuangde800/article/details/9898675参考自该博客。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 1000 + 5;17 18 char str1[maxn],str2[maxn];19 20 struct node21 {22 int len;23 string str;24 }f[maxn][maxn];25 26 int main()27 {28 //freopen("in.txt","r",stdin);29 while(gets(str1+1))30 {31 int len = strlen(str1+1);32 for(int i=len;i>=1;i--)33 str2[i]=str1[len-i+1];34 35 for(int i=0;i<=len;i++)36 {37 f[0][i].len=0;38 f[0][i].str="";39 }40 41 for(int i=1;i<=len;i++)42 {43 for(int j=1;j<=len;j++)44 {45 if(str1[i]==str2[j])46 {47 f[i][j].len=f[i-1][j-1].len+1;48 f[i][j].str=f[i-1][j-1].str+str1[i];49 }50 else51 {52 if(f[i][j-1].len > f[i-1][j].len)53 {54 f[i][j].len=f[i][j-1].len;55 f[i][j].str=f[i][j-1].str;56 }57 else if(f[i][j-1].len < f[i-1][j].len)58 {59 f[i][j].len=f[i-1][j].len;60 f[i][j].str=f[i-1][j].str;61 }62 else63 {64 f[i][j].len=f[i-1][j].len;65 f[i][j].str=min(f[i-1][j].str,f[i][j-1].str);66 }67 }68 }69 }70 71 int maxlen=f[len][len].len;72 string line=f[len][len].str;73 74 if(maxlen&1)75 {76 for(int i=0;i<=maxlen/2;i++)77 printf("%c",line[i]);78 for(int i=maxlen/2-1;i>=0;i--)79 printf("%c",line[i]);80 }81 else82 {83 for(int i=0;i<maxlen/2;i++)84 printf("%c",line[i]);85 for(int i=maxlen/2-1;i>=0;i--)86 printf("%c",line[i]);87 }88 printf("\n");89 }90 return 0;91 }
UVa 11404 回文子序列（LCS求最长回文串长度）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。