UVA 11404 Palindromic Subsequence -

题目地址：http://vjudge.net/problem/UVA-11404

一开始以为是逆序后再求  LICS ， 完全不知道怎么做

然而 只是个  逆序后求 最长且字典序最小的 公共子序列

#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<=(int)(b);++i) #define REPD(i,a,b) for(int i=a;i>=(int)(b);--i) const int maxn=1000+5; struct Node { int len; string s; bool operator < (const Node& n) const { return len == n.len ? s<n.s : len>n.len; } }d[maxn][maxn]; string s,rs; int main(int argc, char const *argv[]) { while(cin>>s){ rs=s; reverse(rs.begin(), rs.end()); s='.'+s; rs='.'+rs; int len=s.length(); REP(i,0,len) { d[0][i].len=d[i][0].len=0; d[0][i].s.clear(); d[i][0].s.clear(); } REP(i,1,len) REP(j,1,len) { if(s[i]==rs[j]) { d[i][j].len=d[i-1][j-1].len+1; d[i][j].s=d[i-1][j-1].s+s[i]; } else d[i][j]=min(d[i-1][j],d[i][j-1]); } int MaxLen=d[len][len].len-1; string MaxS=d[len][len].s; if(MaxLen&1) { REP(i,0,MaxLen/2-1) cout<<MaxS[i]; REPD(i,MaxLen/2,0) cout<<MaxS[i]; } else { REP(i,0,MaxLen/2-1) cout<<MaxS[i]; REPD(i,MaxLen/2-1,0) cout<<MaxS[i]; } printf("\n"); } return 0; }