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

#根据规则递归计算矩阵相乘时的乘法次数
#首先两个矩阵相乘时，A：x*y，B:y*z 则AB相乘的乘法次数为x*z*y
def f(string,d):#string为计算规则，d为矩阵尺寸字典
    if len(string)==1:#最后的结果矩阵，不需要再计算了
        return 0
    for i in range(len(string)):
        if string[i].isupper() and string[i+1].isupper():#找到最先计算的两个矩阵
            n=d[string[i]][0]*d[string[i+1]][1]*d[string[i]][1] #计算乘法次数
            d[string[i]]=[d[string[i]][0],d[string[i+1]][1]]  #将新得到的矩阵记录到字典d中并删除计算过的矩阵，即BC——>B
            d.pop(string[i+1])
            replace_str ='({0}{1})'.format(string[i],string[i+1])#改变计算规则：(A(BC))->(AB)
            new_string=string.replace(replace_str,string[i])
            return n+f(new_string,d)#递归调用，直到得到最后一个矩阵，并累加乘法次数
n=int(input())
d={}
for i in range(n):
    d[chr(ord('A')+i)]=list(map(int,input().split()))
string =input()
print(f(string,d))