51nod_1006 最长公共子序列，输出路径【DP】

题意：

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。


输出最长的子序列，如果有多个，随意输出1个。

思路：

DP，同时DP记录路径。

代码：

string a,b;

int f[1005][1005];

int path[1005][1005];

void _print(int x,int y){

    if(!x||!y) ret;

    int t=path[x][y];

    if(!t)

        _print(x-1,y-1);

    else if(t<0)

        _print(x-1,y);

    else

        _print(x,y-1);

    if(!t) print("%c",a[x-1]);

}

int main(){

    cin>>a>>b;

    int la=a.length(), lb=b.length();

    mem(f,0);

    mem(path,0);

    rep(i,1,la) rep(j,1,lb){

        f[i][j]=max( f[i-1][j],f[i][j-1] );

        if(f[i-1][j]>f[i][j-1]){

            f[i][j]=f[i-1][j];

            path[i][j]=-1;

        }

        else{

            f[i][j]=f[i][j-1];

            path[i][j]=1;

        }

        if(a[i-1]==b[j-1]){

            if(f[i-1][j-1]+1>f[i][j]){

                f[i][j]=f[i-1][j-1]+1;

                path[i][j]=0;

            }

        }

    }

    _print(la,lb); cout<<endl;

    return 0;

}

巴特西

51nod_1006 最长公共子序列，输出路径【DP】

最新文章

热门文章