DataStructureAndAlgorithm/2023210/main.cpp

#include <stdio.h>

struct CalcResult {
    int dim_status;
    int min_multiply_times;
};

unsigned short *tensors;
// unsigned short tensors[66000];
int n = 0, k = 0;
CalcResult *m;
// CalcResult m[10000];
// int* m;
int dim_sizes[32] = {0};

// int precalc[2][1048576] = {0};

inline int tensor_pos(int num, int dim) {
    return k * num + dim;
}

inline int setm(int i, int j, int num) {
    if (j <= i) {
        return 0;
    }

    return m[i * n + j].min_multiply_times = num;
}

inline int getm(int i, int j) {
    if (j <= i) {
        return 0;
    }

    return m[i * n + j].min_multiply_times;
}

inline int setmdim(int i, int j, int d) {
    if (j < i) {
        return 0;
    }

    return m[i * n + j].dim_status = d;
}

inline int getmdim(int i, int j) {
    if (j < i) {
        return 0;
    }

    return m[i * n + j].dim_status;
}

int find_min(int start, int end) {
    if (start == end || getm(start, end) != 0) {
        return getm(start, end);
    }

    int min = 2147483647;
    int needed_multiply_by_d = 1;
    int dim_status = getmdim(start, end);

    // prepare the dims
    for (int i = 0; i < k - 2; i++) {
        if ((dim_status >> i) & 1) {
            needed_multiply_by_d *= dim_sizes[i];
        }
    }
    // for (int i = 0; i <= (k - 2) / 16; i++) {
    //     needed_multiply_by_d *= precalc[i][(dim_status >> (16 * i)) & 0xffff];
    // }

    for (int split_pos = start; split_pos < end; split_pos++) {
        int total_needed = tensors[tensor_pos(start, k - 2)] *
                           tensors[tensor_pos(split_pos, k - 1)] * tensors[tensor_pos(end, k - 1)] *
                           needed_multiply_by_d;
        int left = find_min(start, split_pos), right = find_min(split_pos + 1, end);
        total_needed += left + right;
        if (total_needed < min) {
            min = total_needed;
        }
    }

    setm(start, end, min);
    return min;
}

int clac_min() {
    for (int i = 0; i < n; i++) {
        setm(i, i, 0);
    }

    for (int length = 1; length <= n; length++) {
        for (int start = 0; start <= n - length; start++) {
            int min = 2147483647;
            int needed_multiply_by_d = 1;
            int dim_status = getmdim(start, start + length);

            // prepare the dims
            for (int i = 0; i < k - 2; i++) {
                if ((dim_status >> i) & 1) {
                    needed_multiply_by_d *= dim_sizes[i];
                }
            }

            int matrix_partial_needed = tensors[tensor_pos(start, k - 2)] *
                                        tensors[tensor_pos(start + length, k - 1)] * needed_multiply_by_d;

            for (int split = 0; split < length; split++) {
                int total_needed = matrix_partial_needed * tensors[tensor_pos(start + split, k - 1)] + getm(start, start + split) + getm(start + split + 1, start + length);
                if (total_needed < min) {
                    min = total_needed;
                }
            }
            setm(start, start + length, min);
        }
    }

    return 0;
}

void preparedim(int length) {
    if (length == 1) {
        for (int i = 0; i < n; i++) {
            int cur_stat = 0;
            for (int j = 0; j < k - 2; j++) {
                if (tensors[tensor_pos(i, j)] != 1) {
                    cur_stat |= 1 << j;
                }
            }
            setmdim(i, i, cur_stat);
        }
        return;
    }

    preparedim(length - 1);
    for (int i = length - 1; i < n; i++) {
        setmdim(i - length + 1, i, getmdim(i - length + 1, i - 1) | getmdim(i, i));
    }
}

int main() {
    scanf("%d %d", &n, &k);
    tensors = new unsigned short[n * k];
    // m = new CalcResult[(n + 1) * n / 2];
    m = new CalcResult[n * n];

    for (int i = 0; i < 32; i++) {
        dim_sizes[i] = 1;
    }
    // m = new int[(n + 1) * n / 2];
    for (int tensor_count = 0; tensor_count < n; tensor_count++) {
        for (int dim = 0; dim < k; dim++) {
            scanf("%hu", &tensors[tensor_pos(tensor_count, dim)]);
            if (tensors[tensor_pos(tensor_count, dim)] != 1) {
                dim_sizes[dim] = tensors[tensor_pos(tensor_count, dim)];
            }
        }
    }

    // for (int i = 0; i < 2; i++) {
    //     for (int j = 0; j < 0xffff; j++) {
    //         int prod = 1;
    //         for (int r = 0; r < 16; r++) {
    //             if ((j >> r) & 1) {
    //                 prod *= dim_sizes[i * 16 + r];
    //             }
    //         }
    //         precalc[i][j] = prod;
    //     }
    // }

    preparedim(n);

    // printf("%d\n", find_min(0, n - 1));

    clac_min();
    printf("%d\n", getm(0, n - 1));

    return 0;
}