20分求助

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

shoot_down @ 2022-08-08 07:56:17

#include<iostream>
using namespace std;
int f[100001],b[100005],f2[100005];
int len=1;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(int x)
{
    register int i=1e6;
    while(i&&x/i==0) i/=10;
    if(i){
        for(;i;i/=10){
            putchar(x/i%10+'0');
        }
    }
    else{
        putchar('0');
    }
}
int find(int x)
{
    int l=0,r=len;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(f2[mid]>x)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return r;
}
int main()
{
    int a,ans=-1,cnt=1;
    int n=read();
    for(int i=1;i<=n;i++)
    {
        a=read();
        f[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        b[i]=f[b[i]];
    }
    f2[1]=b[1];
    for(int i=2;i<=n;i++)
    {
        if(b[i]>f2[len])
            f2[++len]=b[i];
        else
        {
            if(b[i]<=f[1])
            {
                f2[1]=b[i];
            }
            else
                f2[find(b[i])]=b[i];
        }

    }
    cout<<len;
    return 0;
}

求助大佬

by zybisfish @ 2023-08-10 21:01:36

给你参照一下我的AC代码吧。你这思路很好的，LCS转LIS。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    register int x = 0,f = 0;
    register char ch = getchar();
    while(ch < 48 || ch > 57) f |= ch == '-',ch = getchar();
    while(ch >=48 && ch <= 57) x = (x << 3)+(x << 1)+(ch ^ 48),ch = getchar();
    return f ? -x : x;
}
int n,a[100010],b[100010];
int main(){
    n = read();
    for(int i=1;i<=n;i++) a[read()] = i;
    for(int i=1;i<=n;i++) b[i] = a[read()];
    int c[100010],len=1;
    c[1] = b[1];
    for(int i=2;i<=n;i++){
        if(b[i] == c[len]) continue;
        if(b[i] > c[len]) c[++len] = b[i];
        else *upper_bound(c+1,c+1+len,b[i]) = b[i];
    }
    printf("%d",len);
    return 0;
}

by zybisfish @ 2023-08-10 21:02:58

你最后一个for循环里面直接改成这样

if(b[i] == f2[len])continue; 
if(b[i] > f2[len]) f2[++len] = b[i];
else f2[find(b[i])] = b[i];

这样改只有90分，我帮你试了好多次了就是改不过来，你自己再查查吧。