60pts 求调

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

PENGQIXUAN_MR_P @ 2024-12-29 16:52:12

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

TLE:#2、#8、#9、#10;


by wuweizhenhahaha @ 2024-12-29 17:13:12

1e5 O(n2) 包T的


by Andy_hpy @ 2025-01-02 20:54:07

用最长上升子序列


|