HDU 1503 Advanced Fruits(LCS変形かつ出力解)

HDU 1503 Advanced Fruits(LCS変形かつ出力解)
http://acm.hdu.edu.cn/showproblem.php?pid=1503
タイトル:
       2つの文字列s 1とs 2を与えて、それらの並列列を出力します.s 1はsの1つのサブシーケンスであり、s 2もsの1つのサブシーケンスであり、sは前の要求に合致するすべての最短文字列です.
分析:
       dp[i][j]=xをs 1列の前i文字とs 2列の前j文字からなる列を表すLCS長をxとする.
       まずLCSのdp配列値を求め、POJ 2250に従います.
http://blog.csdn.net/u013480600/article/details/40743953
       同様のDFSプロセスでs列を出力ことができる.
       大体の考えは:
       dfs(i,j)は、i個の文字(0からカウント)とj個の文字を出力する列の和を表すものとする.
       i=0またはj=0の場合、残りの列を直接出力returnすればよい.
       No(次の3つのプロシージャはi>0およびj>0を保証します):
       s[i-1]==s[j-1]の場合は、まずdfs(i-1,j-1)を、もう一度s 1[i-1](最初の列のi番目の文字)を出力すればよい.
       もしs[i-1]!=s[j-1]の場合:
              dp[i-1][j]>dp[i][j-1]、dfs(i-1,j)、s 1[i-1]を出力すればよい.
              dp[i-1][j]<=dp[i][j-1]、dfs(i,j-1)、s 2[j-1]を出力すればよい.
       (上記の過程をよく体得する)
ACコード:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+5;

int n,m;
int dp[maxn][maxn];
char s1[maxn],s2[maxn];

void dfs(int i,int j)
{
    if(i+j==0) return;
    else if(i==0)//s1       
    {
        for(int k=0;k<j;k++)
            printf("%c",s2[k]);
        return ;
    }
    else if(j==0)//s2       
    {
        for(int k=0;k<i;k++)
            printf("%c",s1[k]);
        return ;
    }

    //       i>0 j>0.
    if(s1[i-1]==s2[j-1]) dfs(i-1,j-1), printf("%c",s1[i-1]);
    else if(dp[i-1][j]>dp[i][j-1]) dfs(i-1,j),printf("%c",s1[i-1]);
    else dfs(i,j-1),printf("%c",s2[j-1]);
}

int main()
{
    while(scanf("%s%s",s1,s2)==2)
    {
        //   
        n=strlen(s1);
        m=strlen(s2);
        memset(dp,0,sizeof(dp));

        //  
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }

        //dfs+  
        dfs(n,m);
        printf("
");
    }
    return 0;
}