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

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

//将输入的矩阵先加入乘号，然后转换为四则运算解法

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>>temp;
    stack<pair<int, int>>matrix;
    stack<char>op;
    while (n--) {
        int x, y;
        cin >> x >> y;
        temp.push_back(pair<int, int>(x, y));
    }
    string s;
    cin >> s;
    int re = 0;
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        auto it = s.begin(); //每次循环时将it重置，因为每次插入后s的大小会变。
        if (((s[i] >= 'A') && (s[i] <= 'Z')) && ((s[i + 1] >= 'A') &&
                (s[i + 1] <= 'Z'))) {   //字母相连时加乘号，类似"A*B"
            s.insert(it + i + 1, '*');
            i = i + 1;
        } else if ((s[i] >= 'A' && s[i] <= 'Z') && (s[i - 1] == ')')) { //"(BC)*D"
            s.insert(it + i, '*');
            i = i + 1;
        } else if ((s[i] >= 'A' && s[i] <= 'Z') && (s[i + 1] == '(')) { //A*(BC)
            s.insert(it + i + 1, '*');
            i = i + 1;
        } else if (s[i]==')'  && (s[i + 1] == '(')) {  //(A*(BC)*(DE))
            s.insert(it + i + 1, '*');
            i = i + 1;
        }
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ')') {
            while (op.top() != '(') {
                pair<int, int> n1 = matrix.top();
                matrix.pop();
                pair<int, int> n2 = matrix.top();
                matrix.pop();
                re += n2.first * n2.second * n1.second;
                matrix.push({ n2.first, n1.second });
                op.pop();
            }
            op.pop();
        } else if (s[i] >= 'A' && s[i] <= 'Z') {
            matrix.push(temp[count]);
            count++;
        } else {
            op.push(s[i]);
        }
    }
    cout << re << endl;
    return 0;

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