题解 | #矩阵乘法计算量估算# C++ 双栈法

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

int main() {
    int num;
    cin >> num;
    unordered_map<char, pair<int, int>> map;
    stack<char> st;
    stack<char> st_op;
    int x, y;
    int c = 'A';
    for (int i = 0; i < num; ++i) {
        cin >> x >> y;
        map[c++] = {x, y};
    }
    string in;
    cin >> in;

    int res = 0;
    for (char s : in) {
        if (s == '(' ) {
            st_op.push(s);
        } else if (isalpha(s)) {
            st.push(s);
        } else {
            st_op.pop();
            char matrix2 = st.top();
            st.pop();
            char matrix1 = st.top();
            st.pop();
            res += map[matrix1].first * map[matrix2].second * map[matrix1].second;
            map[matrix1].second = map[matrix2].second;
            st.push(matrix1);
        }
    }
    cout << res << endl;
    return 0;
}