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

n = int(input().strip())

matrixs = []

for i in range(n):
    matrixs.append(list(map(int, input().strip().split())))

operation = input().strip()

def recursive(operation: str, start:int, matrixs:list[list[int]]):
    temp_matrixs = []
    i = start
    count = 0
    while i < len(operation):
        cur = operation[i]
        if 'A' <= cur <= 'Z':
            if len(temp_matrixs) == 0:
                temp_matrixs.append(matrixs.pop(0))
            else:
                m1 = temp_matrixs.pop()
                m2 = matrixs.pop(0)
                count += m1[0] * m1[1] * m2[1]
                temp_matrixs.append([m1[0], m2[1]])
            i += 1
        elif cur == '(':
            res, pos, inner_count = recursive(operation, i + 1, matrixs)
            count += inner_count
            temp_matrixs.append(res)
            i = pos + 1
        else:
            while len(temp_matrixs) >= 2:
                m1 = temp_matrixs.pop(0)
                m2 = temp_matrixs.pop(0)
                count += m1[0] * m1[1] * m2[1]
                temp_matrixs.insert(0, [m1[0], m2[1]])
            return temp_matrixs[0], i, count

    while len(temp_matrixs) >= 2:
        m1 = temp_matrixs.pop(0)
        m2 = temp_matrixs.pop(1)
        count += m1[0] * m1[1] * m2[1]
        temp_matrixs.insert(0, [m1[0], m2[1]])

    return temp_matrixs[0], len(operation) - 1, count

_, _, count = recursive(operation, 0, matrixs)
print(count)