MLE 啊!!!

P1255 数楼梯

dctc1494 @ 2023-11-05 15:18:14

哪位大佬帮忙看一下我的代码为什么会MLE!

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iterator>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e3 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

LL n, len = 1, f[N][N];

void func(int x) {
    for (LL i = 1; i <= len; ++i) {
        f[x][i] = f[x - 1][i] + f[x - 2][i];
    }
    for (LL i = 1; i <= len; ++i) {
        if (f[x][i] > 9) {
            f[x][i + 1] += f[x][i] / 10;
            f[x][i] %= 10;
        }
    }
    if (f[x][len + 1]) {
        ++len;
    }
}

int main(void) {
    cin >> n;
    f[1][1] = 1;
    f[2][1] = 2;
    for (LL i = 3; i <= n; ++i) {
        func(i);
    }
    for (LL i = len; i; --i) {
        cout << f[n][i];
    }
    cout << endl;

    return 0;
}

by StenvenPig @ 2023-11-05 15:21:36

二维数组开5000*5000以上基本就爆了,更不用说楼主这个了,建议楼主开之前先计算一下


by 2021zjhs005 @ 2023-11-05 15:24:56

@dctc1494

您的数组开得太大了,5000\times 5000 \times 4 (long long 四个字节)。

约是100000000(一亿) 字节,差不多就 MLE 了。

建议以后注意一下。


by Hughpig @ 2023-11-05 15:25:00

@dctc1494 你不会算空间吗


by Argvchs @ 2023-11-05 15:25:22

@dctc1494 不需要 longlong


by Hughpig @ 2023-11-05 15:25:29

数组开太大了


by 2021zjhs005 @ 2023-11-05 15:27:04


by Argvchs @ 2023-11-05 15:28:14

@2021zjhs005 你说得对,但是感觉不如直接 sizeof(long long[5000][5000]) >> 20 = 190(MB)


by Argvchs @ 2023-11-05 15:29:43

@dctc1494 long long 改为 int 可过


by Argvchs @ 2023-11-05 15:34:49

@StenvenPig sizeof(int[5000][5000]) >> 20 = 95(MB),完全可以通过

https://www.luogu.com.cn/record/133506834


by StenvenPig @ 2023-11-05 15:37:09

@Argvchs 抱歉数看错了


| 下一页