90分求助,第二个点wa

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

amxxxxx @ 2022-10-10 23:46:08

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
int n;
int dp[N],ans=0;
int num[N];
int a[N],b[N];
//二分找dp中第一个比x小的元素的下标
int upper(int x,int l,int r){
    int mid;
    while(l<r){
        mid=l+r>>1;
        if(dp[mid]>x)r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)num[a[i]]=i;
    dp[0]=-1;
    for(int i=2;i<=n;i++){
        if(num[b[i]]>dp[ans])
            dp[++ans]=num[b[i]];
        else {int flag=upper(num[b[i]],1,ans);
            dp[flag]=min(dp[flag],num[b[i]]);
        }
    }
    printf("%d",ans);
    system("pause");
    return 0;
}

by northchen @ 2022-10-31 21:37:53

主函数的第四个for,把int i = 2;改成i = 1就能过了


|