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

題目： 點擊打開鏈接

題目大意
給一個字符串，輸出它的最長回文串，如果有多個結果，輸出字典序最小的。

思路
我們都知道把一個字符串逆序後和原字符串進最長公共子序列，可以計算出它的最長回文串長度。
但是這題不僅要輸出回文串，而且還要求是字典序最小的，所以挺難搞的。

設str1是正序字符串，str2是逆序後的字符串
f[i][j].len 表示str1的前i位，str2的前j位，最長公共子串的長度
f[i][j].str 表示str1的前i位，str2的前j位，最長公共子串的最小字典序的字符串

狀態轉移和正常的LCS差不多，只不過增加了記錄字典序最小的字符串

但是最終的f[i][j].str卻並不一定是答案，因為計算出來的最長公共子序列不一定就是回文串

例如：
kfclbckibbibjccbej
jebccjbibbikcblcfk

bcibbibc是他們的LCS，但是卻不是回文串

但是它的前len/2個一定是回文串的前半部分
知道了前len/2，就可以直接構造出回文串的後半部分了
要注意長度的奇偶性問題

代碼

 /**========================================== *
  This is a solution for ACM/ICPC problem * *
  @source：uva-11404 Palindromic Subsequence *
  @type: LCS最小字典序回文串 * 
 @author: shuangde *  
@blog: blog.csdn.net/shuangde800 *
  @email: [email protected] *===========================================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
char str1[MAXN], str2[MAXN];
int n, len;
struct Node{    int len; 
  string str;}f[MAXN][MAXN];
int main(){    Node a, b;
   while(gets(str1+1)){        // reverse        len = strlen(str1+1);  
     for(int i=1; i<=len; ++i)            str2[i] = str1[len+1-i]; 
      // init        for(int i=0;
i<=len;
 ++i)             f[0][i].len = 0, f[0][i].str = "";
       // LCS        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-1][j].len >
 f[i][j-1].len) {                        f[i][j].len = f[i-1][j].len;    
                   f[i][j].str = f[i-1][j].str;             
      } 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 {                        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 maxx = f[len][len].len;     
  string ans = f[len][len].str;
       // output        if(maxx & 1) {       
    for(int i = 0; i < maxx/2; ++i)              
     cout << ans[i];     
      for(int i = maxx/2; i >= 0;
 --i)                cout << ans[i];  
         putchar('\n');     
  } else {            for(int i = 0; i < maxx/2; ++i)   
                    cout << ans[i];        
   for(int i = maxx/2-1; i >= 0;
--i)                cout << ans[i];    
       putchar('\n');    
   }    }    return 0;}