A掉这个题我十分激动,很久没有做dp题了,因为不是很开窍,前两天,累了就趴在床上看算导,翻到动态规划,没想到很顺利地从头到尾看完了,所以就像尝试下dp….这个属于最长公共子序列,以前做过不过这个题需要记录路径,由于路径不唯一,所以是special judge,两个字符串要合并成一个,并且公共部分只输出一次,这其中的细节认真想想就可以做出来..1Y,很高兴~
#include<iostream> #include<cstring> using namespace std; int main() { char a[110],b[110],c[110],temp; int dp[110][110],before[110][110][2]; int i,j,t,count; int lena,lenb; while( cin >> a+1 >> b+1 ) { lena = strlen(a+1); lenb = strlen(b+1); memset( dp,0,sizeof(dp) ); for( i = 1; i <= lena; i++ ) for( j = 1; j <= lenb; j++ ) if( a[i] == b[j] ) { dp[i][j] = dp[i-1][j-1] + 1; before[i][j][0] = i - 1; before[i][j][1] = j - 1; } else { if( dp[i-1][j] > dp[i][j-1] ){ dp[i][j] = dp[i-1][j]; before[i][j][0] = i - 1; before[i][j][1] = j; } else{ dp[i][j] = dp[i][j-1]; before[i][j][0] = i; before[i][j][1] = j - 1; } } //以上是dp的过程,同时记录路径 i=lena;j=lenb; count = 0; while( i && j ) { if( a[i] == b[j] ) c[count++] = a[i]; t = before[i][j][0]; j = before[i][j][1]; i = t; } c[count] = '\0'; for( i = 0,count--; i < count; i++,count-- ) temp=c[i],c[i]=c[count],c[count]=temp; //以上是通过dp的路径,求出公共序列,即c(LCS) for( i = j = 1,t = 0; c[t]!='\0' ; ) { if( a[i] == c[t] && b[j] == c[t] ) cout<<c[t],t++,i++,j++; else if( a[i] == c[t] ) cout<<b[j++]; else if( b[j] == c[t] ) cout<<a[i++]; else cout<<a[i++]<<b[j++]; } cout << a+i << b+j << endl; //以上是合并出来的串 } return 0; }