题解 | #矩阵乘法计算量估算#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int sum = 0, len;
char* p;

int* rr_cc(int r_c[][2], int stack) {
    int* cul_rc = (int*)malloc(sizeof(int) * 2);
    cul_rc[0] = 1;cul_rc[1] = 1;

    int* next_rc;
    while (*p != '\0') {

        if ((*p >= 'A' && *p <= 'Z') && stack == 0) {
            cul_rc[0] = r_c[*p - 'A'][0];
            cul_rc[1] = r_c[*p - 'A'][1];
            p++;
            stack++;
        } else if ((*p >= 'A' && *p <= 'Z') && stack != 0) {
            sum += r_c[*p - 'A'][1] * cul_rc[0] * cul_rc[1];
            cul_rc[1] = r_c[*p - 'A'][1];
            p++;
            stack++;
        } else if (*p == '(' ) {
            p++;
            next_rc = rr_cc(r_c, 0);
            if(*p >= 'A' && *p <= 'Z' )
            {
                cul_rc[0] = next_rc[0];
                cul_rc[1] = next_rc[1];
                next_rc[0] = r_c[*p - 'A'][0];
                next_rc[1] = r_c[*p - 'A'][1];
                p++;
            }else if(*p == '(')
            {
                p++;
                cul_rc[0] = next_rc[0];
                cul_rc[1] = next_rc[1];
                next_rc = rr_cc(r_c, 0);
            }
            sum += cul_rc[0] * cul_rc[1] * next_rc[1];
            cul_rc[1] = next_rc[1];
        } else if (*p == ')') {
            p++;
            break;
        }
    }
    return cul_rc;
}

int main() {
    int num;



    while (scanf("%d", &num) != EOF) {
        int r_c[num][2];

        for (int i = 0; i < num; i++) {
            scanf("%d %d", &r_c[i][0], &r_c[i][1]);
        }
        char str[100];
        scanf("%s", str);




        len = strlen(str);
        p = str+1;

        int* sizee;
        sizee = rr_cc(r_c, 0);
        //printf("%d %d\n",sizee[0],sizee[1]);

        printf("%d", sum);
    }
}