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

import java.util.Scanner;

import java.util.concurrent.atomic.* ;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int mc = in.nextInt();
        int[][] m = new int[mc][2];
        int i = 0;
        while(i++ < mc) {
            int r = in.nextInt();
            int c = in.nextInt();
            m[i-1] = new int[]{r,c};
        }
        String str = in.next();
        // System.out.println(m[2][1]+","+str);
        AtomicInteger acc = new AtomicInteger();
        calc(str, m, acc, new AtomicInteger());
        System.out.println(acc.get());

    }

    static int[] calc(String str, int[][] m, AtomicInteger acc, AtomicInteger len) {
        int[] res = new int[]{1,1};
        // System.out.println(">>"+str);
        for(int i=0;i<str.length();i++) {
            if (str.charAt(i) == '(') {
                // int l = str.lastIndexOf(")");
                AtomicInteger sublen = new AtomicInteger();
                int [] tmp = calc(str.substring(i+1), m, acc, sublen);
                res = mul(res, tmp, acc);
                i = i + sublen.get();
                continue;
            }
            if (str.charAt(i) == ')') {
                len.set(i+1);
                return res;
            }
            int [] tmp = m[str.charAt(i) - 'A'];
            res = mul(res, tmp, acc);
        }
        return res;
    }

    static int[] mul(int [] a, int []b, AtomicInteger acc) {
        if (a[0]==1&&a[1]==1) return b;
        if (b[0]==1&&b[1]==1) return a;
        acc.addAndGet(a[0]*a[1]*b[1]);
        return new int[]{a[0],b[1]};
    }
}