题解 P1439 【【模板】最长公共子序列】

· · 题解

前置知识：最长上升子序列（不懂的自行百度）

这题看似很难，其实只需要一个神转化。

首先，我们来看这样一个问题：给你一个这样的序列：1,2,3,……,n，再给你一个1—n的排列，求他们的最长公共子序列。
这个问题很简单，因为第一个序列是一个严格递增的，所以只要在第二个序列中找到一个上升子序列，那么一定会在第一个序列中出现，这个很好证明。如果要求最长公共子序列，那求最长上升子序列就行了。那回到原来的这个问题，这个问题第一个序列并不是严格递增的。但我们可以给他标号。
如下：

原序列：3 2 1 4 5
  标号：1 2 3 4 5

那我们就把第一个序列变成了刚才的那个问题。注意了，第二个序列如果不做任何改变，那么你就会出问题。而第二个序列的改变方式也是标号。标号方式是和第一个序列一一对应。

p1
原序列：3 2 1 4 5
  标号：1 2 3 4 5
p2
原序列：1 2 3 4 5
  标号：3 2 1 4 4

上面p1中1标号为3，则p2中1的标号也是3。

这样，再对第二个序列的标号求最长上升子序列，就能得出答案了。

上代码吧

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int ans,ma,c[100005],b[100005],r[100005];
int fen(int x)//二分
{
    int le=0,ri=ma,mid;
    while(le<ri)
    {
        mid=(le+ri)/2+1;
        if(r[mid]>=x) ri=mid-1;
        else le=mid;
    }
    return le;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],c[a[i]]=i;//如果直接二重循环枚举的话肯定会超时的，所以借助一个c[]暂时存储c[i]的标号（a[i]的编号就是i）
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        b[i]=c[x];
    }
    for(int i=1;i<=n;i++)
    {
        int l=fen(b[i])+1;
        ans=max(ans,l);
        r[l]=(!r[l]?b[i]:min(r[l],b[i]));
        ma=max(ma,l);
    }//最长上升子序列
    cout<<ans;
    return 0;
}

如果觉得这个蒟蒻写得好的话，能不能点个赞呢/kel