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

#### read
n = int(input())
inList = []
for _ in range(n):
    inList.append(list(map(int, input().strip().split())))
seq = list(input())
#### init
rest = []
count = 0
# A(3,2) B (2,4) ==> 3 * 4 * 2 = 24 
# A (50, 10), B(10*20),   C(20*5)
# ((AB)C) == 50*20*10 + 50 * 20 * 5 = 15000
# A(BC) == 10 * 20 * 5 + 50 * 10 * 5 = 2500 + 1000 = 3500
#### insure ABC or more like ABCD works, keep the final matrix shape.
def get_matrix_mul_count(mList):
    count = 0
    A = mList.pop(0)
    while mList:
        B = mList.pop(0)
        count += A[0] * A[1] * B[1]
        A = [A[0],B[1]]
    return A, count
#### iteration.
while seq:
    i = seq.pop(0)
    if i != ")":
        if i == "(":
            rest.append(i)
        else:
            rest.append(inList[ord(i) - ord("A")])
        continue
    buf = []
    while rest[-1] != "(":
        t = rest.pop(-1)
        buf.insert(0, t)
    rest.pop(-1)
    A, curCount = get_matrix_mul_count(buf)
    count += curCount
    rest.append(A)
# if there is no '()' it is still works.
if len(rest) > 1:
   A, curCount = get_matrix_mul_count(rest)
   count += curCount
print(count)