Make Palindrome

Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

Submit     

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5  6 char str[1005]; 7 int dp[1005][1005],react[1005][1005]; 8  9 int dfs(int x,int y)10 {11     if(x>y)12         return 0;13     if(x==y)14         printf("%c",str[x]);15     else if(react[x][y]==0)16     {17         printf("%c",str[x]);18         dfs(x+1,y-1);19         printf("%c",str[y]);20     }21     else if(react[x][y]==1)22     {23         printf("%c",str[y]);24         dfs(x,y-1);25         printf("%C",str[y]);26     }27     else if(react[x][y]==2)28     {29         printf("%c",str[x]);30         dfs(x+1,y);31         printf("%c",str[x]);32     }33     return 0;34 }35 36 int main()37 {    38     int n;39     int i,j,k;40     while(scanf("%s",str)!=EOF)41     {42         memset(dp,0,sizeof(dp));43         memset(react,0,sizeof(react));44 45         n=strlen(str);46         for(i=n-1;i>=0;i--)47         {48             for(j=i+1;j
          
           dp[i][j-1])57                     {58                         dp[i][j]=dp[i][j-1]+1;59                         react[i][j]=1;60                     }61                     else62                     {63                         dp[i][j]=dp[i+1][j]+1;64                         react[i][j]=2;65                     }66                 }67             }68         }69 70         printf("%d ",dp[0][n-1]);71         dfs(0,n-1);72         printf("\n");73     }74     return 0;75 }