求dalao帮帮忙

paperghost_ls @ 2020-07-01 13:00:53

#include<cstdio>
#define ri register int
using namespace std;
int a[110000],p[110000];
int f[110000],len;
int check(int x)
{
    int l=1,r=len;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(p[f[mid]]>p[x])r=mid;
        else l=mid+1;
    }
    return l;
}
int main()
{
    int n;scanf("%d",&n);
    for(ri i=1;i<=n;i++)scanf("%d",&a[i]);
    for(ri i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        p[x]=i;
    }
    for(ri i=1;i<=n;i++)
    {
        if(p[a[i]]>p[f[len]])f[++len]=a[i];
        else f[check(a[i])]=a[i];
    }
    printf("%d\n",len);
    return 0;
}

by paperghost_ls @ 2020-07-01 13:02:17

这道题我A了，但是校内的oj的最长公共子序列长度是不同而且有重复的，求助求助

by iiawaKL @ 2020-07-01 13:09:09

@paperghost_ls 我看看

by iiawaKL @ 2020-07-01 13:10:00

@paperghost_ls 你先私信我，并且把帖子复制下发给我。我现在在写作业1小时候回复

by jiangby @ 2020-07-01 13:13:43

@paperghost_ls 要求什么时间复杂度和字符集大小

by paperghost_ls @ 2020-07-01 13:15:47

@卖报纸就找我 校内oj要求时间复杂度是O(n2),但是我想尝试一下O(nlogn)的写法，字符集是a~z

by UID341736 @ 2020-07-01 13:25:30

这东西真的能 n^2 吗

by paperghost_ls @ 2020-07-01 13:26:45

@可可萝 是可以的

code:

#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int f[1100][1100];
int main()
{
    char a[1100],b[1100];
    scanf("%s%s",a+1,b+1);
    int alen=strlen(a+1),blen=strlen(b+1);
    for(ri i=1;i<=alen;i++)
        for(ri j=1;j<=blen;j++)
        {
            if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    printf("%d\n",f[alen][blen]);
    return 0;
}

by CHEN_HXI @ 2020-07-01 13:32:07

资瓷

by dzk从不打表 @ 2020-07-01 13:34:52

julao

by CHEN_HXI @ 2020-07-01 13:34:57

大雾