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

主要考察矩阵乘法，基于栈处理表达式。

• 运算量的计算

A*B的运算量：A*B的结果(50*20), 每个元素经历10次运算，即 1w次运算

(AB)C的运算量：结果(50*5)，每个元素经历20次运算，即 5k次运算

• 运算之后的保存

在程序中，AB的结果需要保存，以便下一次与C进行运算。

维护一个当前可用字符('A' + n)，用于存放在栈中，与C比较；同时添加其left, right信息至库中。

• 使用栈处理带括号的表达式

仅看右括号 ')'，若出现则pop两个数进行运算。

eg: ((AB)C) -> (DC) -> E

(A(BC)) -> (AD) -> E

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

int main() {
    int n;
    cin >> n;

    unordered_map<char, pair<int, int>> map;
    for (int i = 0; i < n; i++) {
        cin >> map[(char)('A' + i)].first >> map[(char)('A' + i)].second;
    }

    string s;
    cin >> s;

    stack<char> st;
    int ans_cnt = 0;
    char cur_valid_char = (char)('A' + n);   // 保存新结果

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') continue;
        else if (s[i] != ')') st.push(s[i]);
        else {
            // 假设括号内最多两个
            char b = st.top();
            st.pop();
            char a = st.top();
            st.pop();

            // cout << a << " " << b << endl;
            int left = map[a].first, mid = map[a].second, right = map[b].second;
            // cout << left << " " << mid << " " << right << endl;
            ans_cnt += left * mid * right;

            map[cur_valid_char] = make_pair(left, right);
            st.push(cur_valid_char);

            cur_valid_char = (char)(cur_valid_char + 1);
        }
    }
    cout << ans_cnt << endl;
}