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;
}

 

上一篇:QML中ChartView及子控件的字体设置


下一篇:[DarkBZOJ3754] Tree之最小方差树