P1439 【模板】最长公共子序列（LCS）

先来看一看普通的最长公共子序列

给定字符串A和B，求他们的最长公共子序列

DP做法：

设f[i][j]表示A[1~i]和B[1~j]的最长公共子序列的长度

那么f[i][j]=max(f[i-1][j],f[i][j-1])

在上面的基础上，如果A[i]=B[j]，则f[i][j]=max(f[i][j]，f[i-1][j-1]+1)

代码：

 for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      {

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

        if(a1[i]==a2[j])

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

      }

复杂度为O(mn)

---

那么这道题由于1e5的数据，不论是时间还是空间都会爆炸，就需要考虑另一种做法

我们来观察这个题的特征，发现A和B都是1~n的全排列，也就是说A和B中元素是一样的，考虑充分利用这个特征。

——by pks大佬

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,len;

int atlas[],a[],f[];

int main()

{

    n=read();

    for(int i=,x;i<=n;i++)

    {

        x=read();

        atlas[x]=i;//每个数在序列1出现的位置

    }

    for(int i=,x,now;i<=n;i++)

    {

        x=read();

        now=atlas[x];//在a序列找出x的位置

        if(now>f[len])//如果位置在上一个的后面

        {

            f[++len]=now;

        }

        else

        {

            int j=lower_bound(f+,f++len,now)-f;//在f中找到第一个大于等于now的位置

            f[j]=now;//更新

        }

    }

    cout<<len;

 }