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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[][] matrix = new int[n][2];
        for (int i = 0; i < n; i++) {
            matrix[i][0] = in.nextInt();
            matrix[i][1] = in.nextInt();
        }
        String s = in.next();
        s = s.substring(1, s.length() - 1);
        System.out.println(recursive(matrix, s, 0, s.length() - 1)[2]);
    }
    public static int[] recursive(int[][] matrix, String s, int left, int right) {
        Stack<Integer> stack = new Stack<>();
        int i = left, sum = 0;
        while (i <= right) {
            if (s.charAt(i) == '(') {
                int layer = 0, j = i;
                while (j <= right) {
                    if (s.charAt(j) == '(') {
                        layer++;
                    } else if (s.charAt(j) == ')') {
                        layer--;
                        if (layer == 0) break;
                    }
                    j++;
                }
                int[] res = recursive(matrix, s, i + 1, j - 1);
                sum += res[2];
                if (stack.isEmpty()) {
                    stack.push(res[1]);
                    stack.push(res[0]);
                } else {
                    int r0 = stack.pop(), c0 = stack.pop(), r1 = res[0], c1 = res[1];
                    sum += r0 * c0 * c1;
                    stack.push(c1);
                    stack.push(r0);
                }
                i = j + 1;
            } else if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                int p = s.charAt(i) - 'A';
                if (stack.isEmpty()) {
                    stack.push(matrix[p][1]);
                    stack.push(matrix[p][0]);
                } else {
                    int r0 = stack.pop(), c0 = stack.pop();
                    int r1 = matrix[p][0], c1 = matrix[p][1];
                    sum += r0 * c0 * c1;
                    stack.push(c1);
                    stack.push(r0);
                }
                i++;
            }
        }
        int[] res = new int[3];
        res[2] = sum;
        res[0] = stack.pop();
        res[1] = stack.pop();
        return res;
    }
}