Uva(11404)(Palindromic Subsequence)

链接：https://vjudge.net/problem/UVA-11404
思路：因为最大回文串，也就是前后两端相等，那么很容易想到把原串倒过来然后求最长公共子序列，求出来的值就刚好是最大回文串的长度（因为是和倒置的串求最长公共子序列，所以求出来一定是回文串），关键是如何输出这个回文串。因为有字典序，所以为了方便起见我们用string(重载了min函数可求字段序，虽然比较慢一点)，然后动态规划中条件要改，详见代码
代码：

#include<iostream>
#include<cstring>
using namespace std;
string a,b;
int dp[1001][1001];
string d[1001][1001];

int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
    while(cin>>a){
     b = a;
     for(int i=0;i<a.size();i++)b[i] = a[a.size()-1-i];//倒置原串
        memset(dp,0,sizeof(dp));
       d[0][0] = "";//初始化为空
        for(int i=0;i<a.size();i++){
            for(int j=0;j<b.size();j++){
                if(a[i]==b[j]){
                    dp[i+1][j+1] =  dp[i][j] + 1;
                    d[i+1][j+1] = d[i][j] + a[i];
                }
                    else {
//如果不等就用长度大的那一个的长度和回文
                        if(dp[i][j+1]>dp[i+1][j]){
                            dp[i+1][j+1] = dp[i][j+1];
                        d[i+1][j+1] = d[i][j+1];
                    }
                    else if(dp[i][j+1]<dp[i+1][j]){
                        dp[i+1][j+1] = dp[i+1][j];
                        d[i+1][j+1] = d[i+1][j];
                    }
//如果相等的时候则要比较二者的字典序大小
                    else{
                        dp[i+1][j+1] = dp[i][j+1];
                        d[i+1][j+1] = min(d[i+1][j],d[i][j+1]);
                    }
            }
            }
        }
        int res = dp[a.size()][a.size()];
//要分长度为奇数和偶数进行输出最大回文串
        if(res%2){
        for(int i=0;i<res/2;i++)cout<<d[a.size()][a.size()][i];
        for(int i=res/2;i>=0;i--)cout<<d[a.size()][a.size()][i];
            cout<<endl;
        }
        else{
            for(int i=0;i<res/2;i++)cout<<d[a.size()][a.size()][i];
                for(int i=res/2-1;i>=0;i--)cout<<d[a.size()][a.size()][i];
            cout<<endl;
        }
    }
    return 0;
}