Trip

给出一个长度为n序列\(\{a_i\}\)，长度为m的序列\(\{b_i\}\)，求它们的不同lcs序列按字典序输出，\(n,m\leq 80\)，lcs不超过1000个，字符为26个小写字母。

解

注意，按照传统思路，递推+暴力方案转移+归并排序，时间复杂度\(O(80^3 \times 1000)=O(512000000)=O(5.12\times 10^8)\)，必然会超时，而数据范围又很小，考虑dfs，并用递推的结果优化dfs。

为了让递推结果\(f[i][j]\)表示a序列前i长度，b序列前j长度的最长lcs能起作用，必然是从后往前搜，如果当前的状态能提供的lcs加上已经确定lcs不能为最优解的话，可以剪枝，另外，为了快速确定相同的字符，我们维护\(fa[i][j]\)表示a序列字符i的在\(1\sim j\)的最靠后的位置，fb同理，不难有

\[fa[i][j]=\max(fa[i][j-1],j(a[j]==i+96))
\]

于是维护出这两个东西，以此来dfs剪枝，就可以有很高的效率，不至于tle了。

参考代码：

#include <iostream>

#include <cstdio>

#include <string>

#include <algorithm>

#define il inline

#define ri register

using namespace std;

string a,b,ans[2050];

int dp[101][101],fa[101][101],

    fb[101][101],tot,len;

il int max(int,int);

void dfs(int,int,string),work();

int main(){

    int lsy;cin>>lsy;

    while(lsy--)work(),putchar('\n');

    return 0;

}

void work(){

    cin>>a>>b,tot&=0;

    for(int i(1),j;i<=a.size();++i)

        for(j=1;j<=b.size();++j){

            dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

            if(a[i-1]==b[j-1])dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);

        }

    for(int i(1),j;i<=26;++i){

        for(j=1;j<=a.size();++j)

            if(a[j-1]==i+96)fa[i][j]=j;

            else fa[i][j]=fa[i][j-1];

        for(j=1;j<=b.size();++j)

            if(b[j-1]==i+96)fb[i][j]=j;

            else fb[i][j]=fb[i][j-1];

    }len=dp[a.size()][b.size()];

    dfs(a.size(),b.size(),""),sort(ans+1,ans+tot+1);

    for(int i(1);i<=tot;++i)cout<<ans[i]<<endl;

}

void dfs(int a,int b,string s){

    if(a<0||b<0)return;

    if(s.size()==len)return(void)(ans[++tot]=s);

    for(int i(1);i<=26;++i)

        if(dp[fa[i][a]][fb[i][b]]+s.size()==len)

            dfs(fa[i][a]-1,fb[i][b]-1,(char)(i+96)+s);

}

il int max(int a,int b){

    return a>b?a:b;

}

巴特西

Trip

解

最新文章

热门文章