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

#学到的知识：
#string.rfind('(')#返回从右到左的第一个左括号的字符位置
#string.find(')')#返回从左到右的第一个右括号的字符位置
#若想输出英文26个字母，需要import string，接着string.ascii_uppercase[:26]就可以输出26个字母了

while True:
    try:
        
        import string

        #n是矩阵的个数
        n=int(input())
        #创建字典，例如{'A':[50,10]}
        dict1={}
        for i in range(n):
            dict1[string.ascii_uppercase[i]]=list(map(int,input().strip().split()))

        # order是输入的计算顺序，举例：order='(A(BC))'
        order=input()
        #c是乘法次数
        c=0
        #f是有几个内括号，例如(A(B(CD))))是有一个内括号，(A(B(CD)(EF))))是有两个内括号
        f=1
        
        #计算过程
        #1.按照从左到右的顺序，寻找字符串最后一个左括号，第一个右括号，计算这两个括号之间的对应矩阵的乘法次数
        #2.接着去掉这个左括号和这个右括号
        #3.重复第一步
        #ps:
        #order.rfind('(')#返回从右到左的第一个左括号的字符位置
        #order.find(')')#返回从左到右的第一个右括号的字符位置
        while '(' in order:
            l_b_p=order.rfind('(')  #l_b_p:left_bracket_position左括号的字符位置
            r_b_p=order.find(')')   #r_b_p:right_bracket_position右括号的字符位置

            if l_b_p<r_b_p:  #若第一个左括号的字符位置在倒数第一个右括号的字符位置的右边，也就说明只有一个内括号
                matrix_1=dict1[order[l_b_p+1]]
                matrix_2=dict1[order[l_b_p+2]]
                c=c+matrix_1[0]*matrix_1[1]*matrix_2[1]  #计算乘法次数并加在c上
                dict1['1']=[matrix_1[0],matrix_2[1]]     #将计算所得的新矩阵储存在字典中{'1':[新矩阵]}，并不断迭代
                order=order[:l_b_p]+'1'+order[r_b_p+1:]
            else:
                f=f+1
                r_b_p=order[order.rfind('('):].find(')')+order.rfind('(') #在左括号位置之后寻找右括号的位置
                matrix_1=dict1[order[l_b_p+1]]
                matrix_2=dict1[order[l_b_p+2]]
                c=c+matrix_1[0]*matrix_1[1]*matrix_2[1]    #计算乘法次数并加在c上
                dict1["{}".format(f)]=[matrix_1[0],matrix_2[1]] #将计算所得的新矩阵储存在字典中{'f':[新矩阵]}，并不断迭代
                order=order[:l_b_p]+"{}".format(f)+order[r_b_p+1:]

            
        print(c)

    except:
        break