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

#include<stdio.h>
#include<string.h>

int n;
void compute(char s[],int arr_size[][2],int len,int size_r[]);
int multi_num;

int main(){
    int n;
    int arr_size[20][2];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&arr_size[i][0],&arr_size[i][1]);
    }
    
    int size_r[2];
    char s[200] = {0};
    scanf("%s",s);
    int len = strlen(s);
    
    n = 0;
    multi_num = 0;
    compute(s,arr_size,len,size_r);
    printf("%d\n",multi_num);
     
}

void compute(char s[],int arr_size[][2],int len,int size_r[]){
    // 将属于一个括号的矩阵先保存下来，之后统一计算
    int size[26][2];
    int i = 0;
    
    while(n<len){
        if(s[n]=='('){
            n++;
            compute(s,arr_size,len,size_r);
            size[i][0] = size_r[0];
            size[i][1] = size_r[1];
            i++;
        }
        else if(s[n]==')'){
            n++;
            break;
        }
        else{
            size[i][0] = arr_size[s[n]-'A'][0];
            size[i][1] = arr_size[s[n]-'A'][1];
            n++;
            i++;
        }
        
    }
    for(int j=0;j<i-1;j++){
        multi_num = multi_num + size[j][0]*size[j][1]*size[j+1][1];
        size[j+1][0] = size[j][0];
    }
    size_r[0] = size[0][0];
    size_r[1] = size[i-1][1];
}