hdu 1503 Advanced Fruits （公共子序列 的输出）

思路分析：

在dp LCS的同时记录下状态

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char str1[105],str2[105];
int dp[105][105],pre[105][105];


void print(int i,int j)
{
    if(!i && !j)return;

    if(pre[i][j]==0)
    {
        print(i-1,j-1);
        printf("%c",str1[i-1]);
    }
    else if(pre[i][j]==1)
    {
        print(i-1,j);
        printf("%c",str1[i-1]);
    }
    else
    {
        print(i,j-1);
        printf("%c",str2[j-1]);
    }
}
int main()
{
    while(scanf("%s%s",str1,str2)!=EOF)
    {
        int len1=strlen(str1);
        int len2=strlen(str2);

        memset(dp,0,sizeof dp);

        for(int i=0;i<=len1;i++)
        pre[i][0]=1;
        for(int i=0;i<=len2;i++)
        pre[0][i]=-1;

        for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
        {
            if(str1[i-1]==str2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                pre[i][j]=0;
            }
            else if(dp[i-1][j]>=dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                pre[i][j]=1;
            }
            else
            {
                dp[i][j]=dp[i][j-1];
                pre[i][j]=-1;
            }
        }

        print(len1,len2);
        puts("");
    }
    return 0;
}

hdu 1503 Advanced Fruits （公共子序列 的输出）

原文：http://blog.csdn.net/u010709592/article/details/18843439