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 = 1000 + 5;

char str1[maxn],str2[maxn];

struct node
{
    int len;
    string str;
}f[maxn][maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    while(gets(str1+1))
    {
        int len = strlen(str1+1);
        for(int i=len;i>=1;i--)
            str2[i]=str1[len-i+1];

        for(int i=0;i<=len;i++)
        {
            f[0][i].len=0;
            f[0][i].str="";
        }

        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=len;j++)
            {
                if(str1[i]==str2[j])
                {
                    f[i][j].len=f[i-1][j-1].len+1;
                    f[i][j].str=f[i-1][j-1].str+str1[i];
                }
                else
                {
                    if(f[i][j-1].len > f[i-1][j].len)
                    {
                        f[i][j].len=f[i][j-1].len;
                        f[i][j].str=f[i][j-1].str;
                    }
                    else if(f[i][j-1].len < f[i-1][j].len)
                    {
                        f[i][j].len=f[i-1][j].len;
                        f[i][j].str=f[i-1][j].str;
                    }
                    else
                    {
                        f[i][j].len=f[i-1][j].len;
                        f[i][j].str=min(f[i-1][j].str,f[i][j-1].str);
                    }
                }
            }
        }

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

        if(maxlen&1)
        {
            for(int i=0;i<=maxlen/2;i++)
                printf("%c",line[i]);
            for(int i=maxlen/2-1;i>=0;i--)
                printf("%c",line[i]);
        }
        else
        {
            for(int i=0;i<maxlen/2;i++)
                printf("%c",line[i]);
            for(int i=maxlen/2-1;i>=0;i--)
                printf("%c",line[i]);
        }
        printf("
");
    }
    return 0;
}