TLE4个点求调

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

RJSPZ @ 2022-11-29 13:52:04

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int f[N];
inline 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*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int a[N],b[N];
int n;
int main(){
    n=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
    }
    for(register int i=1;i<=n;i++){
        b[i]=read();
    }
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            f[j]=max(f[j],f[j-1]);
            if(a[i]==b[j]){
                f[j]=max(f[j],f[j-1]+1);
            }
        }
    } 
    write(f[n]);
    return 0;
}

by AC_CSP @ 2022-11-29 13:54:01

@xiaogege

对于 100\% 的数据, n≤10^5


by liangbowen @ 2022-11-29 14:22:38


by Register_int @ 2022-11-29 15:04:57

@xiaogege 能不能看下数据范围亲。


by ReTF @ 2022-11-29 15:16:02


by RJSPZ @ 2022-11-30 12:23:04

@Register_int 谢谢


|