无法定义大矩阵，并且在 C 中使用 malloc 速度很慢

Question

我正在尝试声明一个具有

memo

大小的矩阵

MAX 2000000000

。问题是我在编译时遇到这个错误：

error: size ‘16000000016000000004’ of array ‘memo’ exceeds maximum object size ‘9223372036854775807’
   10 | int memo[MAX + 1][MAX + 1];
      |     ^~~~

我知道这是一个内存问题，但我不知道如何解决。我尝试在 main 的

memo

循环之前使用 malloc 声明

while

，如下所示：

int **memo = (int **)malloc((MAX + 1) * sizeof(int *));
    for (int i = 0; i <= MAX; i++) {
        memo[i] = (int *)malloc((MAX + 1) * sizeof(int));
    }

但这对我来说太慢了，有谁知道声明这个矩阵的有效方法吗？每次扫描新值时，我还必须将矩阵值重置为

-1

。

这是代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX 2000000000 //tiene que ser 2.000.000.000

unsigned int n1,n2,f1,f2;
int i,j;
char next_char;

int memo[MAX + 1][MAX + 1];

void scan_fast(int* int_input){
    *int_input=0;
    next_char=0;
    while( next_char < '0' || next_char > '9' ) // Skip non-digits
        next_char = getchar();
    while( next_char >= '0' && next_char <= '9' )
    {
        (*int_input) = ((*int_input)<<1) + ((*int_input)<<3) + next_char - '0';
        next_char = getchar();
    }
}

int comida(int f1, int f2) {
    /* Se ha terminado el caso */
    if (f1 == 0 && f2 == 0){ return 1; }

    if (memo[f1][f2] != -1) {
        return memo[f1][f2];
    }

    printf("f1: %d, f2: %d\n", f1, f2);
    
    if (f1 >= n1 && f2 >= n2 && comida(f1 - n1, f2 - n2)) {
        memo[f1][f2] = 1;
        return 1;
    } else if (f1 >= n2 && f2 >= n1 && comida(f1 - n2, f2 - n1)){
        memo[f1][f2] = 1;
        return 1;
    } else {
        /* No se ha podido encontrar con este caso */
        memo[f1][f2] = 0;
        return 0;
    }
    
}

int main() {
    scanf("%d %d %d %d", &f1, &f2, &n1, &n2);

    while(!(f1 == 0 && f2 == 0 && n1 == 0 && n2 == 0)) {
        /* Resetear la matriz */
        for (i = 1; i <= MAX; i++) {
            for (j = 1; j <= MAX; j++) {
                memo[i][j] = -1;
            }
        }

        if (comida(f1,f2)) printf("SI\n");
        else printf("NO\n");

        scan_fast(&f1); scan_fast(&f2); scan_fast(&n1); scan_fast(&n2);
    }
    return 0;
}

Answer 1

这个问题的解决方案不是定位这个矩阵，而是使用一个稀疏矩阵，我只定位不是-1的元素（我的程序的初始值）