Palindromic Subsequence

A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.

Constraints

Maximum length of string is 1000.Each string has characters ` a' to ` z' only.

Input

Input consists of several strings, each in a separate line. Input is terminated by EOF.

Output

For each line in the input, print the output in a single line.

Sample Input

aabbaabb
computer
abzla
samhita

Sample Output

aabbaa
c
aba
aha

题意：给定一个字符串，求删除一些字符后，最长的回文字符串，并且要求字典序最小的。

思路：由于要输出字符串，所以在状态转移过程中要保存下字符串，用string就方便很多，然后就是和找最长回文的方法一样了。状态的转移方程为，如果头尾相同，dp[i][j] = dp[i + 1][j - 1] + 2（长度多上首尾多2)如果首尾不同，那么回文长度不增加dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

代码：

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        using namespace std; const int N = 1005; struct State { int value; string str; bool operator > (State &a) { if (value != a.value) return value > a.value; return str < a.str; } } dp[N][N]; int n; char s[N]; int main() { while (~scanf("%s", s + 1)) { n = strlen(s + 1); for (int i = n; i >= 1; i--) for (int j = i; j <= n; j++) { if (s[i] == s[j]) { if (i == j) { dp[i][j].value = 1; dp[i][j].str = s[i]; } else { dp[i][j].value = dp[i + 1][j - 1].value + 2; dp[i][j].str = s[i] + dp[i + 1][j - 1].str + s[j]; } } else { if (dp[i + 1][j] > dp[i][j - 1]) { dp[i][j].value = dp[i + 1][j].value; dp[i][j].str = dp[i + 1][j].str; } else { dp[i][j].value = dp[i][j - 1].value; dp[i][j].str = dp[i][j - 1].str; } } } cout << dp[1][n].str << endl; } return 0; }