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

A(x,y) B(y,z)那么计算量是 xzy 其他的就是如何使用栈处理括号优先级 由于题目中有一句话"保证给出的字符串表示的计算顺序唯一" 这代表 ABC的形式是不存在的, 所以必定会两个符号给出一个括号, 那么遇到)就进行出栈 遇到(不做处理即可(都是从后往前, 并且必定只存在两个矩阵, 所以不需要在stack中加入(符号

stack = []
N=int(input())
D = {}
for i in range(N): D[chr(ord('A')+i)] = list(map(int, input().split()))
s = input()
res = 0
for c in s:
    if c.isalpha():stack.append(c)
    if c == ')' and len(stack)>=2:
        B = stack.pop()
        A = stack.pop()
        res += D[B][1] * D[A][0] * D[A][1]
        D[A][1] = D[B][1]
        stack.append(A)
print(res)