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

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

vector<int> cal(vector<int> x, vector<int> y, int &sum);
//本题只考虑2个矩阵，就没那么复杂，(多个矩阵相乘顺序不定)按题目意思，也是看了其他答主的
int main() {
    int n;
    while (cin >> n) {
        vector<vector<int> > v(n, vector<int>(2, 0));//初始化
        for (int i = 0 ; i < n ; i++) {
            cin >> v[i][0] >> v[i][1];//各矩阵行、列数
        }

        string s;//运算顺序
        cin >> s;

        int len = s.size();
        int k = 0;
        int count = 0;
        stack<vector<int> > st;//用来存储行列数
        for (int i = 0; i < len; i++) {
            if (s[i] == '(') { //遇到左括号跳过
                continue;
            } else if(s[i] == ')'){//遇到右括号弹出栈顶元素两次，分别是两个矩阵1、2的行列数
                vector<int> v1 = st.top();//被乘矩阵2的行列数
                st.pop();
                vector<int> v2 = st.top();//矩阵1的行列数
                st.pop();
                st.push(cal(v2, v1, count)); //将1 * 2的结果压入栈中,最后一次压入栈不影响结果
            }else{//字母入栈
                st.push(v[k++]);
            }
        }
        cout << count << endl;
    }
}

vector<int> cal(vector<int> x, vector<int> y, int& sum) {
    sum += x[0] * x[1] * y[1];//矩阵x的行数*列数*矩阵y的列数
    x[1] = y[1];//新矩阵的列为矩阵y的列
    return x;
}

// 64 位输出请用 printf("%lld")