大佬请看(此题50分)

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

tyh0929 @ 2023-10-18 16:24:29

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],x,dp[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[x]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>x;
        b[i]=a[x];
        dp[i]=1;
    }
    int maxx=-0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(b[i]>b[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
            maxx=max(maxx,dp[i]);
        }
    }
    cout<<maxx;
    return 0;
}

by AC_love @ 2023-10-18 16:27:39

你说有没有一种可能,n^2 通常过不了 1e5


by _ChongYun_ @ 2023-10-18 16:29:58

肯定T啊,正解可以参考题解。


by dmx7u19x @ 2023-10-19 14:19:04

开O2可以拿60分

没办法的办法


|