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

# 从用户输入获取矩阵链的长度  
n = int(input())  
  
# 初始化一个空列表，用于存储矩阵的尺寸  
abs = []  
  
# 通过循环读取每个矩阵的尺寸  
for i in range(n):  
    a, b = list(map(int, input().split()))  
    # 将每个矩阵的尺寸添加到列表中  
    abs = abs + [(a, b)]  
  
# 从用户输入获取一个字符串，表示矩阵链的乘法顺序  
str1 = input()  
  
# 初始化一个临时变量，用于存储当前处理的矩阵的尺寸  
tmp_z = (0, 0)  
  
# 初始化计数器，用于计算总的乘法次数  
count = 0  
  
# 初始化一个栈，用于存储处理过程中的矩阵尺寸  
stack = []  
  
# 遍历输入的字符串，处理矩阵链的乘法  
for i in str1:  
    # 如果遇到左括号，忽略它  
    if i == '(':  
        continue  
    # 如果遇到右括号，执行矩阵乘法  
    elif i == ')':  
        # 弹出栈顶的两个矩阵尺寸  
        tmp_y = stack.pop()  
        tmp_x = stack.pop()  
        # 计算这两个矩阵乘法的乘法次数，并累加到计数器中  
        count += tmp_x[0]*tmp_x[1]*tmp_y[1]  
        # 将乘法结果的新矩阵尺寸压入栈中  
        stack.append((tmp_x[0], tmp_y[1]))  
    # 如果遇到的不是括号，表示是一个矩阵，将其尺寸从列表中取出并压入栈中  
    else:  
        stack.append(abs.pop(0))  
  
# 输出总的乘法次数  
print(count)