P1439 MLE 0分求助

Walker_Sama @ 2022-07-05 16:57:59

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    int dp[10001][10001];
    int a[10001],b[10001];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    printf("%d",dp[n][n]);
    return 0;
}

by Dr_Gilbert @ 2022-07-05 17:02:52

@Toby_Fox

2. 10^5\times 10^5=10^{10}$，$4\times 10^{10}~ \text{B}\approx 4\times 10^4~ \text{MB} \approx 40~\text{GB}

by Walker_Sama @ 2022-07-05 17:08:02

@Dr_Gilbert 所以...怎么压缩...

by Dr_Gilbert @ 2022-07-05 17:16:26

@Toby_Fox 有更优算法，可以自行到题解区学习。

by WanderingTrader @ 2022-07-05 17:19:34

@Toby_Fox 另外，大小较大的数组最好放在全局，不要放在任何一个函数（包括main）里面

by muyang_233 @ 2022-07-05 17:21:22

本题是 a ， b 序列均为 n 的全排列的特殊情况，有特殊做法。

by Walker_Sama @ 2022-07-05 17:21:55

@Dr_Gilbert @WanderingTrader OK thanks