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

这个题很奇怪，看来不用考虑ABC这种三个数连乘的？出栈的时候除了')'，遇到C也要出栈啊；

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int mul[20][2];
int sum = 0;
void eval(stack<pair<int, int>>& st) {
    auto [a, b] = st.top();
    st.pop();
    auto [c, d] = st.top();
    st.pop();
    // cd矩阵在前，ab矩阵在后
    // cout<< c << " " << d << " " << a << " " << b << endl; 
    // if (a != d) cout << "calculate error" << endl;
    sum += c * d * b;
    st.push(pair<int, int>(c, b));
}
int main() {
    int n;
    while (cin >> n) {
        // sum = 0;
        string input;
        stack<pair<int, int>> st;
        for (int i = 0; i < n; ++i) {
            cin >> mul[i][0] >> mul[i][1];
        }
        cin >> input;
        // int m = input[0] == '(' ? input.size() - 1: input.size();
        for (int i = 0; i < input.size(); ++i) {
            // 只要不是'('都会引发出一次计算
            char c = input[i];
            if (c == ')' ) {
                eval(st);
            }else if(c != '('){
                st.push(make_pair(mul[c - 'A'][0], mul[c - 'A'][1]));
                // if (i > 0 && input[i - 1] != '(') {
                //     eval(st);
                // }
            }
        }
        cout << sum << endl;
    }
}
// 64 位输出请用 printf("%lld")