HDU 1503 Advanced Fruits[ LCS ]

HDU 1503 Advanced Fruits[ LCS ]

題目：HDU 1503

思路：先求出最長公共子序列，記錄路徑。後進行拼接。

代碼

#include
#include
#include
#include
#include
#include
#define mod 1000000007
using namespace std;

typedef long long LL;

int dp[110][120];
char x[100],y[100];
struct node{
    int x,y;
    char c;
}ans[220];

void LIS_len(int lx,int ly)
{
    memset(dp,0,sizeof dp);
    for(int i=1;i<=lx;i++){
        for(int j=1;j<=ly;j++){
            if(x[i-1]==y[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
}

int main()
{
    while(cin>>x>>y)
    {
        int lx=strlen(x);
        int ly=strlen(y);
        LIS_len(lx,ly);

        int i=lx,j=ly;
        if(dp[lx][ly]==0)
        {
            printf("%s%s\n",x,y);
            continue;
        }
        int len=0;
        while(i&&j)
        {
            if(dp[i][j]==dp[i-1][j-1]+1&&x[i-1]==y[j-1])
            {
                ans[len].x=i;
                ans[len].y=j;
                ans[len++].c=x[i-1];
                i--;j--;
            }
            else if(dp[i-1][j]>=dp[i][j-1])
                i--;
            else
                j--;
        }
        i=j=1;
        for(int k=len-1;k>=0;k--)
        {
            while(i!=ans[k].x)
            {
                printf("%c",x[i-1]);
                i++;
            }
            //cout<
：