题意：打印两个串，但是LCS只打印一次
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; char a[110],b[110]; int dp[110][110]; char m[110][110]; void Find(int i,int j) { if(i==0&&j==0)return; if(m[i][j]=='\\') { Find(i-1,j-1); printf("%c",a[i-1]); } else if(m[i][j]=='|') { Find(i-1,j); printf("%c",a[i-1]); } else if(m[i][j]=='-') { Find(i,j-1); printf("%c",b[j-1]); } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); while(~scanf("%s%s",a,b)) { int l1=strlen(a); int l2=strlen(b); memset(m,'\\',sizeof(m)); for(int i=0;i<=l1;i++) { dp[i][0]=0; m[i][0]='|'; } for(int i=0;i<=l2;i++) { dp[0][i]=0; m[0][i]='-'; } for(int i=1;i<=l1;i++) { for(int j=1;j<=l2;j++) { if(a[i-1]==b[j-1]) 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]; m[i][j]='|'; } else { dp[i][j]=dp[i][j-1]; m[i][j]='-'; } } } Find(l1,l2); printf("\n"); } }