题目

给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。

样例：

输入
5
1 2 3 4 5
1 2 3 4 5
5
1 2 3 5 4
1 2 3 4 5

输出
5
4

思路

读题会发现这个跟普通的最长公共子序列不太一样，他的自己的序列没有重复的数。我们会发现最长公共子序列这个序列的下标是单调递增的，在读题发现他让我们求得仅仅仅仅知识最长公共子序列的长度，把这个序列的下标放进一个数组里，答案就是这个数组的长度。那么问题似乎就变成了求最长子序列。

那么这个问题为什么能变成最长子序列的问题？

> 因为公共子序列中值的相同的，所以数组2中公共子序列中的值放到数组1中数组下标仍然相同
> 所以：求公共子序列因为不用求具体的序列是多少，我们转化为求公共子序列的下标，因为下标是递增的！！！
> 所以转化为求最长上升子序列,这个序列是值下表的序列

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],b[N],id[N],q[N];

int n,m;
int main(){
    //ios::sync_with_stdio(false);
    //cin>>n;
    scanf("%d",&n);//测试了一下scanf比关了同步慢一些
    memset(id,-1,sizeof id);//初始化所有为-1，没有这个数就为-1，桶计数。
    for(int i=0;i<n;i++){
        //cin>>a[i];
        scanf("%d",&a[i]);
        id[a[i]]=i;//存所有数的下标
    }
    q[0]=-1;
    int len=0;
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        int pos=id[b[i]];//找b中的数在a中得位置
        if(pos==-1) continue;//a中没有b中的数，跳过
        int l = 0, r = len;//二分查找第一个小于等于pos的数
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(q[mid] < pos) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = pos;//加入，有可能加入中间，也有可能加在最后。
        len = max(len, r + 1);//得到最大值，答案不一定是在最后，也有可能在中间，但一定有答案
    }
    cout<<len<<endl;
}