【51NOD-0】1006 最长公共子序列Lcs

【算法】经典DP

【题解】经典lcs，输出路径可以记录上一个有效节点就是有点麻烦。

因为开始时写法不太明确，打印结果时初始循环地方搞错了，后来修正写法时忘了改过来，调了好久。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int maxn=1010;
int f[maxn][maxn],n,m;
char a[maxn],b[maxn];
struct cyc{int a,b,c;}pre[maxn][maxn];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);m=strlen(b+1);
    memset(f,0,sizeof(f));
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            if(f[i-1][j]>f[i][j-1])
            {
                f[i][j]=f[i-1][j];
                if(pre[i-1][j].c)pre[i][j].a=i-1,pre[i][j].b=j;else pre[i][j]=pre[i-1][j];
                pre[i][j].c=0;
            }
            else
            {
                f[i][j]=f[i][j-1];
                if(pre[i][j-1].c)pre[i][j].a=i,pre[i][j].b=j-1;else pre[i][j]=pre[i][j-1];
                pre[i][j].c=0;
            }
            if(a[i]==b[j]&&f[i-1][j-1]+1>f[i][j])
            {
                f[i][j]=f[i-1][j-1]+1;
                if(pre[i-1][j-1].c)pre[i][j].a=i-1,pre[i][j].b=j-1;else pre[i][j]=pre[i-1][j-1];
                pre[i][j].c=1;
            }
        }
    }
    int x=n,y=m;
    char ch[maxn];int tot=-1;
    while(x!=0||y!=0)
    {
//        printf("c=%d
",pre[x][y].c);
        if(pre[x][y].c)ch[++tot]=a[x];
        int xx=pre[x][y].a;
        y=pre[x][y].b;
        x=xx;
    }
    for(int i=tot;i>=0;i--)printf("%c",ch[i]);
    return 0;
}