ZOJ 1953 Advanced Fruits(LCS)

于 2011年02月5日 发布在 算法&&ACM 跳到评论

ZOJ 1953 Advanced Fruits

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;
}

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)