uva 11404 Palindromic Subsequence(LCS回文串，最小字典序)

本是古典何须时尚 2021-12-12 16:45 245阅读 0赞

## 题意：给一个字符串，输出它的最长回文串，如果有多个结果，输出字典序最小的。 ##

## 分析：把原串反转求LIS，因为转移时不断求字典序最小导致后半部分可能并非回文，只需要前半部分。例如下面这个例子： ##

s = 1 5 2 4 3 3 2 4 5 1
    reverse(s) = 1 5 4 2 3 3 4 2 5 1
           LCS = 1 5 2 3 3 4 5 1

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1010;
    int len[N][N];
    string s[N][N];
    char s1[N],s2[N];
    
    int main(){
        while(~scanf("%s",&s1[1])){
            int l = strlen(s1+1);
            for(int i=1;i<=l;i++)
                s2[i] = s1[l-i+1];
            for(int i=0;i<=l;i++){
                len[0][i] = len[i][0] = 0;
                s[0][i] = s[i][0] = "";
            }
            for(int i=1;i<=l;i++){
                for(int j=1;j<=l;j++){
                    if(s1[i] == s2[j]){
                        len[i][j] = len[i-1][j-1]+1;
                        s[i][j] = s[i-1][j-1]+s1[i];
                    }
                    else{
                        if(len[i-1][j] > len[i][j-1]){
                            len[i][j] = len[i-1][j];
                            s[i][j] = s[i-1][j];
                        }
                        else if(len[i-1][j] < len[i][j-1]){
                            len[i][j] = len[i][j-1];
                            s[i][j] = s[i][j-1];
                        }
                        else{
                            len[i][j] = len[i-1][j];
                            s[i][j] = min(s[i-1][j],s[i][j-1]);
                        }
                    }
                }
            }
            int anslen = len[l][l];
            string ans = s[l][l];
            if(anslen & 1){
                for(int i=0;i<anslen/2;i++)
                    printf("%c",ans[i]);
                for(int i=anslen/2;i>=0;i--)
                    printf("%c",ans[i]);
            }
            else{
                for(int i=0;i<anslen/2;i++)
                    printf("%c",ans[i]);
                for(int i=anslen/2-1;i>=0;i--)
                    printf("%c",ans[i]);
            }
            printf("\n");
        }
        return 0;
    }