可以麻烦帮我看一下吗?

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

_fanjin_ @ 2023-11-23 20:43:55

新人,TLE了,代码如下

#include<iostream>
using namespace std;

const int MAXN = 1e5 + 5;

int a[MAXN],b[MAXN];
int f[2][MAXN];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    } 
    for(int i=1;i<=n;i++){
        for( int j=1;j<=n;j++){
            if(a[i]==b[j])f[i%2][j] = f[(i-1+2)%2][j-1]+1;
            else f[i%2][j]=max(f[(i - 1 + 2)%2][j],f[i%2][j-1]);
        }
    }
    cout<<f[n%2][n];
    return 0;
}

by Running_a_way @ 2023-11-23 20:45:59

@fanjin 你这 O(n^2) TLE 是正常的哦,请学习更优的做法。


by wangjiawen @ 2023-11-23 20:48:54


by _fanjin_ @ 2023-11-23 20:53:51

谢谢大佬


by _little_Cabbage_ @ 2023-11-23 21:01:44

@fanjin 这是DP题


by Special_Tony @ 2024-05-15 16:11:34

@_littleCabbage 他也是dp,只是方法假了


|