题目：HDU 1503

思路：先求出最长公共子序列，记录路径。后进行拼接。

代码

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define mod 1000000007 using namespace std; typedef long long LL; int dp[110][120]; char x[100],y[100]; struct node{ int x,y; char c; }ans[220]; void LIS_len(int lx,int ly) { memset(dp,0,sizeof dp); for(int i=1;i<=lx;i++){ for(int j=1;j<=ly;j++){ if(x[i-1]==y[j-1]) { dp[i][j]=dp[i-1][j-1]+1; } else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } int main() { while(cin>>x>>y) { int lx=strlen(x); int ly=strlen(y); LIS_len(lx,ly); int i=lx,j=ly; if(dp[lx][ly]==0) { printf("%s%s\n",x,y); continue; } int len=0; while(i&&j) { if(dp[i][j]==dp[i-1][j-1]+1&&x[i-1]==y[j-1]) { ans[len].x=i; ans[len].y=j; ans[len++].c=x[i-1]; i--;j--; } else if(dp[i-1][j]>=dp[i][j-1]) i--; else j--; } i=j=1; for(int k=len-1;k>=0;k--) { while(i!=ans[k].x) { printf("%c",x[i-1]); i++; } //cout<
        
         
 ：