30分,只对了1,2,4三个点,能过样例,求助

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

huangx607087 @ 2019-08-19 20:31:11

#include <bits/stdc++.h>
using namespace std;
int n,m,Ans;
int a[607087],b[607087];
int f[607087],g[607087];//f:映射,g:动归 
int gett(int L,int R,int Now)//二分查找
{
    while(L<R)
    {
        int Mid=(L+R)/2;
        if(g[Mid]<=f[b[Now]]) L=Mid+1;
        else R=Mid;
    }
    return L;
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) scanf("%d",&b[i]);
    memset(g,70,2428348);
    g[0]=0;
    for(i=1;i<=n;i++) f[a[i]]=max(f[a[i]],i);
    for(i=1;i<=n;i++)
    {
        if(f[b[i]]>g[Ans]) g[++Ans]=f[b[i]];
        else 
        {
            int tmp=gett(0,Ans,i);
            g[tmp]=min(g[tmp],f[b[tmp]]);
        }
    }
    printf("%d\n",Ans);
    return 0;
}

|