AcWing夏季每日一题--最长公共子序列

https://www.acwing.com/problem/content/3513/

AcWing夏季每日一题--最长公共子序列

 

 其中一个串不重复是公共子序列问题转换为上升子序列问题的一个充要条件。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int q[N],id[N];
int main()
{
    int n;
    cin>>n;
    memset(id,-1,sizeof id);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        id[x]=i;
    }
    int tt=0;
    q[0]=-1;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        int k=id[x];
        if(k==-1) continue;
        int l=0,r=tt;
        while(l<r){//找到小于k的最大的
            int mid=l+r+1>>1;
            if(q[mid]>=k) r=mid-1;
            else l=mid;
        }
        q[r+1]=k;
        tt=max(tt,r+1);
    }
    cout<<tt<<endl;
    return 0;
}

 

AcWing夏季每日一题--最长公共子序列

上一篇:windows10环境下的RabbitMQ安装步骤(图文)


下一篇:AcWing 144. 最长异或值路径(Trie)