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

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> attri(n, vector<int>(2));
    for (int i = 0; i < n; ++i) {
        cin >> attri[i][0] >> attri[i][1];
    }
    string str;
    cin >> str;
    stack<int> matrix;
    int left = 0, right = 0, sum = 0;
    vector<int> vec;
    for (int i = 0; i < str.length(); ++i) {
        if (str[i] != ')') {
            if (str[i] == '(')
                left++;
            else
                vec.push_back(str[i]-'A');
        } else {
            if (++right > left)
                break; //测试用例中有‘)’个数多于‘(’个数的情况，故加入该判断语句。
            int y = vec.back();
            vec.pop_back();
            int x = vec.back();
            vec.pop_back();
            sum += attri[x][0] * attri[x][1] * attri[y][1];
            attri[x][1] = attri[y][1];
            vec.push_back(x);
        }
    }
    cout << sum << endl;

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