UVa 11404 回文子序列（LCS求最长回文串长度）

https://vjudge.net/problem/UVA-11404

题意：

给定一个由小写字母组成的字符串，删除其中的0个或多个字符，使得剩下的字母（顺序不变）组成一个尽量长的回文串。如果有多解，输出字典序最小的解。

思路：

首先，最长回文子串的长度可以通过正序字符串和逆序字符串进行LCS得出。

但是这道题目麻烦的是还要输出这个回文串，并且字典序得最小。

应用的主要还是LCS的思想方法，不过在进行状态转移的时候，再加上字符串的状态转移。

不过最后得到的字符串不一定是回文串，但是它的前一半肯定是回文串的一半，那么后面的一半只需要根据前面的就可以得出。

http://blog.csdn.net/shuangde800/article/details/9898675参考自该博客。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn =  + ;

 char str1[maxn],str2[maxn];

 struct node

 {

     int len;

     string str;

 }f[maxn][maxn];

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(gets(str1+))

     {

         int len = strlen(str1+);

         for(int i=len;i>=;i--)

             str2[i]=str1[len-i+];

         for(int i=;i<=len;i++)

         {

             f[][i].len=;

             f[][i].str="";

         }

         for(int i=;i<=len;i++)

         {

             for(int j=;j<=len;j++)

             {

                 if(str1[i]==str2[j])

                 {

                     f[i][j].len=f[i-][j-].len+;

                     f[i][j].str=f[i-][j-].str+str1[i];

                 }

                 else

                 {

                     if(f[i][j-].len > f[i-][j].len)

                     {

                         f[i][j].len=f[i][j-].len;

                         f[i][j].str=f[i][j-].str;

                     }

                     else if(f[i][j-].len < f[i-][j].len)

                     {

                         f[i][j].len=f[i-][j].len;

                         f[i][j].str=f[i-][j].str;

                     }

                     else

                     {

                         f[i][j].len=f[i-][j].len;

                         f[i][j].str=min(f[i-][j].str,f[i][j-].str);

                     }

                 }

             }

         }

         int maxlen=f[len][len].len;

         string line=f[len][len].str;

         if(maxlen&)

         {

             for(int i=;i<=maxlen/;i++)

                 printf("%c",line[i]);

             for(int i=maxlen/-;i>=;i--)

                 printf("%c",line[i]);

         }

         else

         {

             for(int i=;i<maxlen/;i++)

                 printf("%c",line[i]);

             for(int i=maxlen/-;i>=;i--)

                 printf("%c",line[i]);

         }

         printf("\n");

     }

     return ;

 }

巴特西

UVa 11404 回文子序列（LCS求最长回文串长度）

最新文章

热门文章