hdu 1503 最大公共子序列+输出路径

?

?

#include
  
   
#include
   
     #include
     
     using namespace std
     ; int max
     (int a
     ,int b
     ) { return a
     >a
     ?a
     :b
     ; } char str1
     [110
     ],str2
     [110
     ]; int mark
     [110
     ][110
     ]; int deal
     (int i
     ,int j
     ) { 
      if(i
     ==0
     &&j
     ==0
     ) return 0
     ; if(mark
     [i
     ][j
     ]==0
     ) { deal
     (i
     -1
     ,j
     -1
     ); printf
     ("%c"
     ,str1
     [i
     -1
     ]); } else if(mark
     [i
     ][j
     ]==1
     ) { deal
     (i
     -1
     ,j
     ); printf
     ("%c"
     ,str1
     [i
     -1
     ]); } else if(mark
     [i
     ][j
     ]==2
     ) { deal
     (i
     ,j
     -1
     ); printf
     ("%c"
     ,str2
     [j
     -1
     ]); } return 0
     ; } int main() { int i
     ,j
     ; int dp
     [110
     ][110
     ]; while(~scanf
     ("%s%s"
     ,str1
     ,str2
     )) { int len1
     =strlen
     (str1
     ); int len2
     =strlen
     (str2
     ); memset
     (dp
     ,0
     ,sizeof(dp
     )); for(i
      = 0
     ;i
     <=len1
     ;i
     ++) mark
     [i
     ][0
     ] = 1
     ; for(i
      = 0
     ;i
     <=len2
     ;i
     ++) mark
     [0
     ][i
     ] = 2
     ; for(i
     =1
     ;i
     <=len1
     ;i
     ++) { for(j
     =1
     ;j
     <=len2
     ;j
     ++) { if(str1
     [i
     -1
     ]==str2
     [j
     -1
     ]) { dp
     [i
     ][j
     ]=dp
     [i
     -1
     ][j
     -1
     ]+1
     ; mark
     [i
     ][j
     ]=0
     ; } else { //dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 
      if(dp
     [i
     -1
     ][j
     ]>=dp
     [i
     ][j
     -1
     ]) { dp
     [i
     ][j
     ]=dp
     [i
     -1
     ][j
     ]; mark
     [i
     ][j
     ]=1
     ; } else { mark
     [i
     ][j
     ]=2
     ; dp
     [i
     ][j
     ]=dp
     [i
     ][j
     -1
     ]; } } } } //printf("****\n"); deal
     (len1
     ,len2
     ); printf
     ("\n"
     ); } return 0
     ; }
    
   
  

?