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

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

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> t;
    for(int i=0;i<n;++i){
        int x,y;
        cin >>x>>y;
        t.push_back({x,y});
    }
    stack<pair<int,int>> st;
    string s;
    cin >> s;
    int sum=0;
    for(char ch:s){
        if(ch==')'){
            pair<int,int> x=st.top();
            st.pop();
            pair<int,int> y=st.top();
            st.pop();
            sum+=x.second*x.first*y.first;
            st.push({y.first,x.second});
        }
        else if(ch<='Z'&&ch>='A'){
            st.push(t[ch-'A']);
        }

    }
    cout << sum;
}
// 64 位输出请用 printf("%lld")