题目 字符串的LCS，输出解我比较不会，dp的时候记录从哪里转移来的，之后要一步一步转移回去把解存起来然后输出。
代码语言：javascript复制#include<cstdio>
#include<cstring>
#define N 102
#define M 32
int n,m,dp[N][N],ans[N][N];
char s1[N][M],s2[N][M],str[N][M];
void solve(){
memset(dp,0,sizeof dp);
memset(ans,0,sizeof ans);
int i,j,t,ti;
for (i=1;i<=n;i )
for (j=1;j<=m;j )
if (strcmp(s1[i-1],s2[j-1])==0)
dp[i][j]=dp[i-1][j-1] 1;
else if(dp[i-1][j]>dp[i][j-1]){
dp[i][j]=dp[i-1][j];
ans[i][j]=1;//从s1转移来
}else
dp[i][j]=dp[i][j-1];
i=n,j=m;
t=dp[n][m];
while(i&&j)
if(strcmp(s1[i-1],s2[j-1])==0){
memcpy(str[--t],s1[i-1],sizeof s1[i-1]);
i--;j--;
}
else{
ti=i;
i-=ans[i][j];
j-=1^ans[ti][j];//ans=0则是s2转移来的，故j--
}
for(i=0;i<dp[n][m];i ) printf("%s ",str[i]);
printf("n");
}
int main(){
while (~scanf("%s",&s1[n]))
if (s1[n][0]=='#'){
while (scanf("%s",&s2[m])&&s2[m][0]!='#') m ;
solve();
n=m=0;
}
else n ;
return 0;
}
