Palindromic Subsequence
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 struct Node 9 {10 int len;11 string str;12 }dp[1005][1005];13 14 int main()15 {16 int l;17 char str1[1005],str2[1005];18 int i,j,k;19 while(scanf("%s",str1+1)!=EOF)20 {21 l=strlen(str1+1);22 for(i=1;i<=l;i++)23 str2[i]=str1[l-i+1];24 25 for(i=0;i<=l;i++)26 dp[0][i].len=0,dp[i][0].len=0,dp[0][i].str="",dp[i][0].str="";27 28 for(i=1;i<=l;i++)29 {30 for(j=1;j<=l;j++)31 {32 if(str1[i]==str2[j])33 {34 dp[i][j].len=dp[i-1][j-1].len+1;35 dp[i][j].str=dp[i-1][j-1].str+str1[i];36 }37 else38 {39 if(dp[i][j-1].len>dp[i-1][j].len)40 {41 dp[i][j].len=dp[i][j-1].len;42 dp[i][j].str=dp[i][j-1].str;43 }44 else if(dp[i-1][j].len>dp[i][j-1].len)45 {46 dp[i][j].len=dp[i-1][j].len;47 dp[i][j].str=dp[i-1][j].str;48 }49 else50 {51 dp[i][j].len=dp[i-1][j].len;52 dp[i][j].str=min(dp[i-1][j].str,dp[i][j-1].str);53 }54 }55 }56 }57 58 int n=dp[l][l].len;59 string ans=dp[l][l].str;60 61 if(n%2==0)62 {63 for(i=0;i =0;i--)68 {69 printf("%c",ans[i]);70 }71 }72 else73 {74 for(i=0;i =0;i--)79 {80 printf("%c",ans[i]);81 }82 }83 printf("\n");84 }85 return 0;86 }