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

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

char zimu[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
              'Q','R','S','T','U','V','W','X','Y','Z'};
int pos=0;

int cixu(char c)
{
    int i;
    for(i=0;i<26;i++)
        if(c==zimu[i]) return i;
    return 0;
}

int trans(char str[],int in[][2],int b[])//返回运算次数，得到矩阵为b[0]*b[1]
{
    int len=strlen(str);
    int number[100];
    int i=0,j,n;
    b[0]=0;
    b[1]=0;
    int a[2]={0,0};
    while(pos<len)
    {
        if(str[pos]=='('&&str[pos-1]!=')')
        {
            pos++;
            number[i++]=trans(str, in,a);
        }
        
        if(str[pos-1]==')')
        {
            if(a[1]!=0) number[i++]=b[0]*b[1]*a[1];
            if(b[0]==0) b[0]=a[0];
            b[1]=a[1];
            
            a[0]=0;
            a[1]=0;
            
            if('A'<=str[pos]&&str[pos]<='Z')
            {
                n=cixu(str[pos]);
        
                a[0]=in[n][0];
                a[1]=in[n][1];
                if(a[1]!=0) number[i++]=b[0]*b[1]*a[1];
                
                a[0]=0;
                a[1]=0;
            
                if(b[0]==0) b[0]=in[n][0];
                b[1]=in[n][1];
            }
            else if(str[pos]=='(') 
            {    
                pos++;
                number[i++]=trans(str, in,a);
                continue;
            }
        }
        else if('A'<=str[pos]&&str[pos]<='Z')
        {
            n=cixu(str[pos]);
            
            a[0]=in[n][0];
            a[1]=in[n][1];
            if(a[1]!=0) number[i++]=b[0]*b[1]*a[1];
            
            a[0]=0;
            a[1]=0;
            
            if(b[0]==0) b[0]=in[n][0];
            b[1]=in[n][1];
        }
        if(str[pos]==')') 
        {
            pos++;
            break;
        }
        pos++;
    }
    int sum=0;
    for(j=0;j<i;j++) {sum=sum+number[j];}
    return sum;
}

int main()
{
    int n;
    scanf("%d",&n);
    int in[n][2];
    int i;
    for(i=0;i<n;i++) scanf("%d%d",&in[i][0],&in[i][1]);
    char str[100];
    scanf("%s",str);
    
    int a[2]={0,0};
    printf("%d",trans(str, in,a));
    return 0;
}