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

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> row(n);
    vector<int> col(n);
    for(int i = 0; i < n; ++i) {
        cin >> row[i] >> col[i];
    }
    string expression;
    cin >> expression;
    stack<char> st;
    int ans = 0;
    for(const char& c: expression) {
        if(c != '(' && c != ')') st.push(c);
        else if(c == ')') {
            char c1 = st.top(); st.pop();
            char c2 = st.top(); st.pop();
            ans += row[c2-'A'] * row[c1-'A'] * col[c1-'A'];
            st.push(c1);
            row[c1-'A'] = row[c2-'A'];//让B = A*B  所以更新B的行数 方便后续计算
        }
    }
    cout << ans << endl;
    return 0;
}