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

#第一个矩阵为A，第二矩阵为B，若字母不是这个意思，下面代码无法通过
n=int(input())
dic={}  #存储所有矩阵
for i in range(n):
    dic[chr(ord('A')+i)]=list(map(int,input().split())) #将所有矩阵按字母A~Z存到字典里，值为（行，列）
s=input()
s1=[]  
num=0
for i in s:    #遍历字符串
    if i!=')':  #未遇到')'时，一直压栈
        s1.append(i)
    else:        #遇到')',开始循环弹出两个字母，用其对应的矩阵运算  
        while True:
            if s1[-2]=='(':  #遇到'('，删除它，并跳出循环
                s1.pop(-2)
                break
            else:
                b=s1.pop()		#弹出两个字母
                a=s1.pop()
                if dic[a][1]!=dic[b][0]: #排除这两个矩阵是（m,n）（c,m）情况
                    a,b=b,a          #让两个矩阵变成（c,m）（m,n）,保证乘法次数和运算后的矩阵没问题
                    dic[a+'*'+b]=[dic[a][0],dic[b][1]]  #将运算后的矩阵保存到字典里
                    s1.append(a+'*'+b)  运算后的新矩阵，将其对应的key值入栈
                else:
                    dic[a+'*'+b]=[dic[a][0],dic[b][1]]
                    s1.append(a+'*'+b)
                num+=dic[a][0]*dic[a][1]*dic[b][1]	#将矩阵相乘的次数累加到num
print(num)