输入

第1行：字符串A

第2行：字符串B

(A,B的长度 <= 1000)

输出

输出最长的子序列，如果有多个，随意输出1个。

输入样例

abcicba

abdkscab

输出样例

abca

思路就是先求最长公共子序列，然后再根据路径逆推，找到匹配点。

#include<iostream>

#include<queue>

#include<algorithm>

#include<set>

#include<cmath>

#include<vector>

#include<map>

#include<stack>

#include<bitset>

#include<cstdio>

#include<cstring>

//---------------------------------Sexy operation--------------------------//

#define cini(n) scanf("%d",&n)

#define cinl(n) scanf("%lld",&n)

#define cinc(n) scanf("%c",&n)

#define cins(s) scanf("%s",s)

#define coui(n) printf("%d",n)

#define couc(n) printf("%c",n)

#define coul(n) printf("%lld",n)

#define speed ios_base::sync_with_stdio(0)

#define file  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

//-------------------------------Actual option------------------------------//

#define Swap(a,b) a^=b^=a^=b

#define Max(a,b) a>b?a:b

#define Min(a,b) a<b?a:b

#define mem(n,x) memset(n,x,sizeof(n))

#define mp(a,b) make_pair(a,b)

//--------------------------------constant----------------------------------//

#define INF  0x3f3f3f3f

#define maxn  1005

#define esp  1e-9

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

//------------------------------Dividing Line--------------------------------//

string a,b,ans;

int dp[maxn][maxn];

int main()

{

    ans.clear();

    cin>>a>>b;

    a=' '+a;

    b=' '+b;

    int la=a.size();

    int lb=b.size();

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

    {

        for(int j=1;j<lb;j++)

        {

            if(a[i]==b[j])

                dp[i][j]=dp[i-1][j-1]+1;

            else

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

        }

    }

    int m=la-1,n=lb-1;

    while(dp[m][n])

    {

        if(dp[m][n]==dp[m-1][n]) m--;

        else if(dp[m][n-1]==dp[m][n]) n--;

        else

        {

            if(a[m]!=' ')

            ans=a[m]+ans;

            m--,n--;

        }

    }

    cout<<ans<<endl;

}

巴特西

51NOD 1006 最长公共子序列 Lcs 动态规划 DP 模板题板子

输入

输出

输入样例

输出样例

最新文章

热门文章

巴特西

51NOD 1006 最长公共子序列 Lcs 动态规划 DP 模板题 板子

输入

输出

输入样例

输出样例

最新文章

热门文章

51NOD 1006 最长公共子序列 Lcs 动态规划 DP 模板题板子