90分求助(T_T)~

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

cxm1024 @ 2019-07-30 08:26:27

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int t[100010];
int f[100010];
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        t[x]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[i]=t[x];
    }
    f[0]=0;
    f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(f[ans]<a[i])
        {
            f[++ans]=a[i];
        }
        else
        {
            f[upper_bound(f+1,f+ans+1,a[i])-f]=a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

by team109 @ 2019-07-30 08:33:30

90分是WA还是TLE?
头像好评


by 奇骥 @ 2019-10-22 20:34:59

我刚刚也卡在90了。后来发现,ans应该初始化成1,而不是0.


|