1 //Accepted    208 KB    0 ms 2 //最长公共上升子序列+输出 3 //dp 4 //输出时用的递归输出，注意条件判断 5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 using namespace std; 9 const int imax_n = 105;10 const int imax_stringlen = 32;11 char s1[imax_n][imax_stringlen];12 char s2[imax_n][imax_stringlen];13 int dp[imax_n][imax_n];14 int n1,n2;15 int max(int a,int b)16 {17     return a>b?a:b;18 }19 void Dp()20 {21     memset(dp,0,sizeof(dp));22     for (int i=1;i<=n1;i++)23     {24         for (int j=1;j<=n2;j++)25         {26             dp[i][j]=max(dp[i-1][j],dp[i][j-1]);27             if (strcmp(s1[i],s2[j])==0)28             dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);29         }30     }31 }32 void output(int i,int j)33 {34     if (dp[i][j]==0) return ;35     if (dp[i-1][j]==dp[i][j])36     {37         output(i-1,j);38         return ;39     }40     if (dp[i][j-1]==dp[i][j])41     {42         output(i,j-1);43         return ;44     }45     if (dp[i-1][j-1]+1==dp[i][j])46     {47         output(i-1,j-1);48         if (dp[i][j]==1)49         {50             printf("%s",s1[i]);51             return ;52         }53         else54         {55             printf(" %s",s1[i]);56             return ;57         }58     }59     return ;60 }61 int main()62 {63     while (scanf("%s",s1[1])!=EOF)64     {65         int k=1;66         k++;67         while (scanf("%s",s1[k]) && s1[k][0]!=‘#‘)68         k++;69         n1=k-1;70         k=1;71         while (scanf("%s",s2[k]) && s2[k][0]!=‘#‘)72         k++;73         n2=k-1;74         Dp();75         output(n1,n2);76         printf("\n");77     }78     return 0;79 }