【算法】经典DP

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

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

#include
      
       #include
       
        #include
        
         #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\n",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;}