解疑

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

Lazy_Durant @ 2024-04-06 18:48:15

每次二分找第一个比他大的,不应该接着更新len吗?

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,x,a1[N],a2[N],trans[N],b[N],len;
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a1[i]);
        trans[a1[i]]=i;
    }
    for(int i=1; i<=n; i++) {
        scanf("%d",&x);
        a2[i]=trans[x];
    }
    for(int i=1; i<=n; i++) {
        if(a2[i]>b[len]) {
            b[++len]=a2[i];
            continue;
        }
        int k=lower_bound(b+1,b+len+1,a2[i])-b;
        b[k]=a2[i];
        //len=k;  这一句为什么不要
    }
    printf("%d\n",len);
    return 0;
}

by Nazq @ 2024-04-12 21:09:20

@Lazy_Durant len 记录的是当前 LIS 的长度。\ 如果能构成更长的上升子序列,len 才往后移。\ 如果不能更新出更长的上升子序列, \ 对于一个上升子序列,其结尾元素越小,到后面的元素越可能接到其后面,越可能凑出更长的上升子序列。 所以此过程更新的是子序列结尾元素,并没有更新出更长的上升子序列,所以 len 不更新。


|