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

#include <bits/stdc++.h>

using namespace std;
int a[20][2];
string s;

int main(){
    int n;
    while(cin >> n){
        for(int i=0;i<n;i++)
            cin >> a[i][0] >> a[i][1];//输入矩阵的行列
        cin >>s;
        stack<pair<int,int>> st;//栈存储矩阵的行列
        int len=s.size();
        int res=0;
        for(int i=0;i<len;i++){//遍历字符串
            if(s[i]==')'){//如果是右括号，则栈弹出两个元素，并累加乘法次数
                auto y=st.top();
                st.pop();
                auto x=st.top();
                st.pop();
                if(x.second==y.first){
                    res+=x.second*x.first*y.second;
                    st.push({x.first,y.second});//形成新的矩阵并入栈
                }else if(x.first==y.second){
                    res+=x.first*x.second*y.first;
                    st.push({x.second,y.first});
                }
                
            }else if(s[i]!='('){//如果是字符，则直接入栈
                int t=s[i]-'A';
                st.push({a[t][0],a[t][1]});
            }
        }
        cout << res << endl;//输出答案
    }
    
    return 0;
}