【模板】最长公共子序列(LCS)。

看过好多人的博客，感觉要么是太复杂要么就是太不容易理解。

那就亲自动手写一个通俗易懂的。

先定义两个数组，第一个数组为主，用第二个数组来匹配第一个，看能有多少可以对应上的。

所以，其实第一个数组的内容可以暂时不考虑，当知道它对应了第二个数组的哪个数字就BINGO了。

顺着这个思路继续想就可以得到以下思路：

把第一个数组离散化（记录第一个数组变成什么）后的数组是满足上升的关系。

现在的问题就变成了求一个最长不下降序列。

二话不说上代码。

------------------------------------------一道华丽的分割线------------------------------------------

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cctype>

#define rg register

#define int long long

using namespace std;

inline int read(){

    rg int s=0,f=0;

    rg char ch=getchar();

    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();

    while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();

    return f?-s:s;

}

int n,len;

const int MAX=100010;

int a1[MAX],a2[MAX],f[MAX],b[MAX],c[MAX];

signed main(){

    n=read();

    for(rg int i=1;i<=n;++i){

        a1[i]=read();

        c[a1[i]]=i;

    }

    for(rg int i=1;i<=n;++i){

        a2[i]=read();

    }

    for(rg int i=1;i<=n;++i){

        if(c[a2[i]]>b[len]){

            b[++len]=c[a2[i]];

            f[i]=len;

            continue;

        }

        int k=lower_bound(b+1,b+len+1,c[a2[i]])-b;

        b[k]=c[a2[i]];

        f[i]=k;

    }

    printf("%d\n",len);

    return 0;

}

巴特西

【模板】最长公共子序列(LCS)。

最新文章

热门文章