感觉转为LCS 其实就可以在弄一个数组，然后按照ＬＣＳ的形式，，
但是错了。。
而且自己不会表示输出的答案序列。。
看了别人的。
他用的循环不太懂。。大概就是按照判断会问的思路
然后又看了别人的，感觉挺好http://blog.csdn.net/l123012013048/article/details/44493921
至少和ＬＣＳ的代码像，注意答案是前半部分的重复
#include<bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define sf scanf #define pf printf #define bug1 printf("bug1\n"); #define N 1005 #define M 10 #define INF 1e9 #define LL long long #define inf 0x3f3f3f3f char s1[N],s2[N]; struct Node { string ans; int len; bool operator >(const Node&a){ if(this->len!=a.len)return this->len>a.len; return this->ans<a.ans; } }dp[N][N]; char ans[N][N]; int main(){ while(~sf("%s",s1+1)){ mem(ans,0); int len=strlen(s1+1); for(int i=1;i<=len;++i)s2[len-i+1]=s1[i]; for(int i=1;i<=len;++i){ dp[0][i].len=dp[i][0].len=0; dp[0][i].ans=dp[i][0].ans=""; } for(int i=1;i<=len;++i){ for(int j=1;j<=len;++j){ if(s1[i]==s2[j]){ dp[i][j].ans=dp[i-1][j-1].ans+s1[i]; dp[i][j].len=dp[i-1][j-1].len+1; } else { if(dp[i-1][j].len>dp[i][j-1].len){ dp[i][j].ans=dp[i-1][j].ans; dp[i][j].len=dp[i-1][j].len; } else if(dp[i-1][j].len<dp[i][j-1].len){ dp[i][j].ans=dp[i][j-1].ans; dp[i][j].len=dp[i][j-1].len; } else{ dp[i][j].ans=min(dp[i-1][j].ans,dp[i][j-1].ans); dp[i][j].len=dp[i][j-1].len; } } } } int Len = dp[len][len].len; string str = dp[len][len].ans; if(Len & 1) { int mid = Len / 2; for(int i = 0; i < mid; i++) cout << str[i]; for(int i = mid; i >= 0; i--) cout << str[i]; } else{ int mid = Len / 2; for(int i = 0; i < mid; i++) cout << str[i]; for(int i = mid-1; i >= 0; i--) cout << str[i]; } puts(""); } }
