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

此题和HJ54表达式求值比较像。

'''
假设矩阵乘法的矩阵存在a中,计算的规则存在s中。
a = [[m,n], [n,p], [p,q]]
s = (A(BC))

1. if遇到左括号,找对应的右括号,递归。括号内的res更新, shape计算完入栈
2. elif遇到字符,该字符与A减法得到数组中的索引,ord(s[l]) - ord('A'), 将对应数组的索引取出入栈
3. if 入栈元素==2,计算矩阵计算次数res,并将计算得到的矩阵shape入栈
注意的点：
    这里res作为global, 按理是返回shape和res,这里方便期间,只返回shape
    t2的标识符是计算(AB)时,最后len(st)=1, return会报错。
'''

import sys

# 递归函数
def f(s, l, r):
    global res
    st = [] # 保存当前矩阵的栈
    t2 = 'flag_use' # 使用标识符
    while l <= r:
        if s[l] == '(':
            j = l + 1
            level = 1
            # 循环找到匹配的右括号
            while j <= r:
                if s[j] == '(':
                    level += 1
                elif s[j] == ')':
                    level -= 1
                    if level == 0:
                        # 递归求解子问题
                        t = f(s[l+1:j], 0, len(s[l+1:j]) - 1)  # 矩阵shape
                        # 后序入栈
                        st.append(t)
                        break
                j += 1
            l = j
        elif s[l].isalpha():
            x = ord(s[l]) - ord('A')
            st.append((a[x][0], a[x][1]))
        if len(st)==2:
            # 弹出栈顶元素,构造新的矩阵
            t2 = st.pop()
            t1 = st.pop()
            res += t1[0] * t1[1] * t2[1] # 矩阵计算次数
            st.append((t1[0], t2[1]))
        l += 1
    return (t1[0], t2[1]) if type(t2) != str else None  # 矩阵shape

# for line in sys.stdin:
n = int(input().strip())
res = 0
a = []
for i in range(n):
    a_i = list(map(int, input().split()))
    a.append(a_i)
s = input().strip()

f(s, 0, len(s) - 1)
print(res)