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

#include<iostream>
#include <stack>
#include <vector>

using namespace std;

int main(){
    int res = 0;
    int n ;
    cin >> n;

    // 创建一个存放pair的数组
    vector<pair<int, int>> v;
    pair<int, int> tmpPair;
    for(int i = 0; i < n; ++i){
        cin >> tmpPair.first >> tmpPair.second;
        v.push_back(tmpPair);
    }

    string str ;
    cin >> str;

    stack<pair<int, int>> st;
    for(auto c : str){
        // 遇到右括号开始做运算
        if( c == ')' ){
            pair<int, int> a = st.top();
            st.pop();
            pair<int, int> b = st.top();
            st.pop();

            // 累加运算次数
            res += b.first * b.second * a.second;
            st.push(make_pair(b.first, a.second));

        }else if(c != '('){
            // 向栈中插入数据
            st.push(v[c-'A']);
        }   
    }
    // 打印输出
    cout << res << endl;
    return 0;
}