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

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        Map<Character, Matrix> map = new HashMap<>();
        List<Matrix> list = new ArrayList<>();
        char name = 'A';
        for (int i = 0; i < n; i++) {
            String[] line = sc.nextLine().split(" ");
            int left = Integer.parseInt(line[0]);
            int right = Integer.parseInt(line[1]);
            map.put(name, new Matrix(left, right));
            name++;
        }
        String s = sc.nextLine();
        Result r = calMatrix(map, s);
        System.out.println(r.value);
    }
    public static Result calMatrix(Map<Character, Matrix> map, String s) {
        int resVal = 0;
        Matrix resMatrix = null;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetter(c)) {
                Matrix m = map.get(c);
                if (resMatrix == null) {
                    resMatrix = m;
                } else {
                    resVal = resVal + resMatrix.left * m.left * m.right;
                    resMatrix = new Matrix(resMatrix.left, m.right);
                }
            }
            if (c == '(') {
                int count = 0;
                int j = i + 1;
                for (; j < s.length(); j++) {
                    if (s.charAt(j) == '(') {
                        count++;
                    }
                    if (s.charAt(j) == ')') {
                        if (count == 0) {
                            break;
                        }
                        count--;
                    }
                }
                Result r = calMatrix(map, s.substring(i + 1, j));
                if (resMatrix == null) {
                    resVal = resVal  + r.value;
                    resMatrix = r.mx;
                } else {
                    resVal = resVal + resMatrix.left *  r.mx.left * r.mx.right + r.value;
                    resMatrix = new Matrix(resMatrix.left, r.mx.right);
                }
                i = j;
            }
        }
        return new Result(resVal, resMatrix);
    }
}
class Matrix {
    public int left;
    public int right;
    public Matrix() {}
    public Matrix(int left, int right) {
        this.left = left;
        this.right = right;
    }
}
class Result {
    public int value;
    public Matrix mx;
    public Result() {}
    public Result(int value, Matrix matrix) {
        this.value = value;
        this.mx = matrix;
    }
}