跟了一个教程学结果就只有20分

6lszxz @ 2022-01-31 10:29:16

#include "iostream"
#include "cstring"

int a[100005];
int b[100005];
int n;

int compare(int i,int j){
    if(i==n){
        if(b[j]==a[i]){
            return 1;
        } else{
            return 0;
        }
    }
    if(j==n){
        if (a[i]==b[j]){
            return 1;
        } else{
            return 0;
        }
    }
    if(a[i]==b[j]){
        return 1+ compare(i+1,j+1);
    } else{
        return std::max(compare(i,j+1), compare(i+1,j));
    }
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    printf("%d", compare(1,1));
}

by HarmonicQuadrilatera @ 2022-01-31 10:46:19

@6lszxz 你的程序跑的太慢了

by HarmonicQuadrilatera @ 2022-01-31 10:46:36

建议学习：“时间复杂度”

by HarmonicQuadrilatera @ 2022-01-31 10:47:47

就会发现你的程序的复杂度是 O(2^{2n})，会超时

正解复杂度 O(n\log n)

by WanderingTrader @ 2022-01-31 10:49:11

@6lszxz 您的教程……怕不是假的

by int32 @ 2022-01-31 11:06:26

什么鬼教程

by LYqwq @ 2022-01-31 11:07:34

您的教程……怕不是假的

这么高的时间复杂度能有 \sout 20 分都是奇迹了（

by 林聪 @ 2022-01-31 11:10:02

说不定是先展示一下高复杂度的做法，然后再讲优化呢

by Escapism @ 2022-01-31 11:39:03

@6lszxz 这时间复杂度......太可怕了

正解DP

by 6lszxz @ 2022-01-31 12:00:10

改了一下，现在是50分，如果要过一百分的话这个数组会爆栈叭QAQ

#include "iostream"
#include "cstring"

int a[100005];
int b[100005];
int n;
int answer[1005][1005];

int compare(int i,int j){
    if(i==n){
        if(b[j]==a[i]){
            answer[i][j]=1;
            return answer[i][j];
        } else{
            answer[i][j]=0;
            return answer[i][j];
        }
    }
    if(j==n){
        if (a[i]==b[j]){
            answer[i][j]=1;
            return answer[i][j];
        } else{
            answer[i][j]=0;
            return answer[i][j];
        }
    }
    if(a[i]==b[j]){
        if(answer[i][j]!=-1){
            return answer[i][j];
        } else{
            answer[i][j] = 1+ compare(i+1,j+1);
            return answer[i][j];
        }
    } else{
        if(answer[i][j]!=-1){
            return answer[i][j];
        } else{
            answer[i][j] = std::max(compare(i,j+1), compare(i+1,j));
            return  answer[i][j];
        }
    }
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    memset(answer,-1,sizeof (answer));
    printf("%d", compare(1,1));
}