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

n = int(input())
mat = {}
for i in range(n):
    r, c = map(int, input().split())
    # 映射 A、B、C... 到对应矩阵的(行,列)
    mat[chr(ord('A') + i)] = (r, c)

s = input().strip()
stack = []
total = 0

for ch in s:
    if ch == '(':
        stack.append('(')
    elif ch == ')':
        # 1. 弹出括号内所有矩阵，直到遇到左括号
        temp = []
        while stack[-1] != '(':
            temp.append(stack.pop())
        stack.pop()  # 弹出左括号
        temp = temp[::-1]  # 反转回正确顺序
        
        # 2. 括号内矩阵依次相乘
        cur_r, cur_c = temp[0]
        for i in range(1, len(temp)):
            n_r, n_c = temp[i]
            total += cur_r * cur_c * n_c
            cur_c = n_c  # 更新为新矩阵的列数
        stack.append((cur_r, cur_c))
    else:
        # 字母矩阵直接入栈
        stack.append(mat[ch])

stack = stack[::-1]
while len(stack) > 1:
    m1 = stack.pop()  # 取左边第一个矩阵
    m2 = stack.pop()  # 取左边第二个矩阵
    total += m1[0] * m1[1] * m2[1]
    # 相乘结果插回栈头部
    stack.append(0, (m1[0], m2[1]))

print(total)