Palindromic Subsequence
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <string> 5 #include <iostream> 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 else 38 { 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 else 50 { 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<n/2;i++) 64 { 65 printf("%c",ans[i]); 66 } 67 for(i=n/2-1;i>=0;i--) 68 { 69 printf("%c",ans[i]); 70 } 71 } 72 else 73 { 74 for(i=0;i<n/2;i++) 75 { 76 printf("%c",ans[i]); 77 } 78 for(i=n/2;i>=0;i--) 79 { 80 printf("%c",ans[i]); 81 } 82 } 83 printf(" "); 84 } 85 return 0; 86 }