洛谷 P1439 【模板】最长公共子序列

这题不是LCS的裸题啊……。。基本上照抄的题解:
https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int a[100005],b[100005],map[100005],f[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];map[a[i]]=i;}
    for(int i=1;i<=n;i++){cin>>b[i];f[i]=0x7fffffff;}
    int len=0;
    f[0]=0;
    for(int i=1;i<=n;i++){
        int l=0,r=len,mid;
        if(map[b[i]]>f[len])f[++len]=map[b[i]];
        else{
            while(l<r){
                mid=(l+r)>>1;
                if(f[mid]>map[b[i]])r=mid;
                else l=mid+1;
            }
            f[l]=min(map[b[i]],f[l]);
        }
    }
    cout<<len;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注