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

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        stack<char> sym;
        vector<vector<int>> ax(n, vector<int>(2, 0));
        for (int i = 0; i < n; ++i) {
            cin >> ax[i][0] >> ax[i][1];
        }
        string pattern;
        long sum = 0;
        cin >> pattern;
        for (int i = 0; i < pattern.size(); ++i) {
            if (isalpha(pattern[i]) || pattern[i] == '(') {
                sym.push(pattern[i]);
            } else if (pattern[i] == ')') {
                char tem;
                while (sym.top() != '(') {
                    char y = sym.top();
                    sym.pop();
                    char x = sym.top();
                    sym.pop();
                    tem = x;
                    sum += ax[x - 'A'][0] * ax[x - 'A'][1] * ax[y - 'A'][1];
                    ax[x - 'A'][1] = ax[y - 'A'][1];
                }
                sym.pop();
                sym.push(tem);
            }
        }
        cout << sum << endl;
    }
    return 0;
}