TLE四个点求助QWQ

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

qishaohan @ 2024-03-23 21:06:39

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e5+10;
int f[maxn];
int x[maxn],y[maxn],s[maxn],b[maxn];
int lenx,leny,ans=0;
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        s[x]=i;
    }
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        b[i]=s[x];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(b[i]>b[j])f[i]=max(f[i],f[j]);
        }
        f[i]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

t了2,8,9,10四个点,帮帮我


by _Weslie_ @ 2024-03-23 21:08:16

@qishaohan 因为你的算法问题。

题目数据范围是 10^5,而你的是 n^2 的。


by XuYueming @ 2024-03-23 21:08:22

@qishaohan \Theta(n^2) 不 T 才怪嘞


|