题解：SP33 TRIP - Trip

cwxcplh · 2026-01-27 14:00:55 · 题解

很简单的一道题。

我们很容易想到原题实际上就是让我们输出两个字符串的最长公共子序列有哪些。首先写出求最长公共子序列长度的 DP 转移方程：

for(int i=1;i<=n1;i++)
{
    for(int j=1;j<=n2;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(s1[i]==s2[j])
        {
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
}

这里因为字符串长度最大是 80，所以时间复杂度肯定没问题。

现在我们考虑怎么输出方案。我们可以选择使用一个数组来记录转移到当前状态的上一个状态有哪些。在输出时只需要用 dfs 逆向枚举回去就可以了。

代码实现：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
code by plh;
namespace fastio
{
    inline int read()
    {
        int z=0,f=1;
        char c=getchar();
        if(c==EOF)
        {
            exit(0);
        }
        while(c<'0'||c>'9')
        {
            if(c==EOF)
            {
                exit(0);
            }
            if(c=='-')
            {
                f=-1;
            }
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            z=z*10+c-'0';
            c=getchar();
        }
        return z*f;
    }
    inline void write(int x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        static int top=0,stk[106];
        while(x)
        {
            stk[++top]=x%10;
            x/=10;
        }
        if(!top)
        {
            stk[++top]=0;
        }
        while(top)
        {
            putchar(char(stk[top--]+'0'));
        }
    }
    inline void write(string s)
    {
        for(auto i:s)
        {
            putchar(i);
        }
    }
}
using namespace fastio;
int n1,n2,b[86][86],f[86][86];
//b 数组用来标记能从哪些状态转移过来（使用二进制）
string s1,s2;
set<string>s;
map<tuple<int,int,string>,bool>mp;
void print(int x,int y,string ss)
{
    if(!x||!y)
    {
        s.insert(ss);
        return;
    }
    if(mp[make_tuple(x,y,ss)])//标记防止重复计算，同时剪枝
    {
        return;
    }
    mp[make_tuple(x,y,ss)]=1;
    if(b[x][y]&1)
    {
        print(x-1,y,ss);
    }
    if(b[x][y]&2)
    {
        print(x,y-1,ss);
    }
    if(b[x][y]&4)
    {
        print(x-1,y-1,s1[x]+ss);//注意要倒着拼
    }
}
signed main()
{
    int T;
    T=read();
    while(T--)
    {
        cin>>s1>>s2;
        n1=s1.size();
        n2=s2.size();
        s1=" "+s1;
        s2=" "+s2;
        for(int i=0;i<=n1;i++)
        {
            for(int j=0;j<=n2;j++)
            {
                f[i][j]=0;
                b[i][j]=0;
            }
        }
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if(f[i-1][j]==f[i][j])
                {
                    b[i][j]|=1;
                }
                if(f[i][j-1]==f[i][j])
                {
                    b[i][j]|=2;
                }
                if(s1[i]==s2[j])
                {
                    if(f[i-1][j-1]+1>f[i][j])
                    {
                        b[i][j]=4;
                    }
                    else if(f[i-1][j-1]+1==f[i][j])
                    {
                        b[i][j]|=4;
                    }
                    f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                }
            }
        }
        print(n1,n2,"");
        for(auto i:s)
        {
            write(i);
            putchar('\n');
        }
        s.clear();
    }
    return 0;
}