poj - 2250 题解

题意：魔改版的LCS问题。序列是单词序列

解法：原版LCS的序列元素是数字，想办法把数字替换成单词就解决了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
string a[4000];
string b[4000];
int f[4000][4000];
int la=0;
int lb=0;
string res[4000];
bool get_res(int x,int y,int z)
{
    if(z==f[la][lb]+1)
    {
        return true;
    }
    if(x*y==0)
    {
        return false;
    }
    if(a[x]==b[y])
    {
        res[z]=a[x];
        if(get_res(x-1,y-1,z+1))
        {
            return true;
        }
    }
    else
    {
        if(f[x][y]==f[x][y-1])
        {
            if(get_res(x,y-1,z))
            {
                return true;
            }
        }
        if(f[x][y]==f[x-1][y])
        {
            if(get_res(x-1,y,z))
            {
                return true;
            }
        }
    }
    return false;
}
int main()
{
    string s;
    while(cin>>s)
    {
        bool flag=false;
        la=0;
        lb=0;
        a[++la]=s;
        while(true)
        {
            cin>>s;
            if(s=="#")
            {
                if(flag)
                {
                    break;
                }
                flag=true;
                continue;
            }
            if(!flag)
            {
                a[++la]=s;
            }
            else
            {
                b[++lb]=s;
            }
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=la;i++)
        {
            for(int j=1;j<=lb;j++)
            {
                if(a[i]==b[j])
                {
                    f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                }
                else
                {
                    f[i][j]=max(f[i][j-1],f[i-1][j]);
                }
            }
        }
        get_res(la,lb,1);
        for(int i=f[la][lb];i>=1;i--)
        {
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}