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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt(); // 矩形的个数
            //记录行数和列数
            int[] row = new int[n];
            int[] column = new int[n];
            for (int i = 0; i < n; i++) {
                row[i] = in.nextInt();
                column[i] = in.nextInt();
            }
            in.nextLine();
            String s = in.nextLine();
            System.out.println(getResult(s, row, column));
        }
    }

    private static int getResult(String s, int[] row, int[] column) {
        char[] arr = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = arr[i];
            if (c >= 'A' && c <= 'Z') {
                stack.push(row[c - 'A']);
                stack.push(column[c - 'A']);
            }

            if (c == ')') {
                if (!stack.isEmpty() && stack.size() >= 4) {
                    int y0 = stack.pop();
                    int x0 = stack.pop();
                    int y1 = stack.pop();
                    int x1 = stack.pop();
                    //求矩阵x1 x y1 与 矩阵x0 x y0的相乘时的乘积次数
                    sum += x1 * y1 * y0;
                    
                    //计算结果
                    stack.push(x1);
                    stack.push(y0);           
                }
            }
        }
        return sum;
    }
}