题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
主要考察矩阵乘法,基于栈处理表达式。
- 运算量的计算
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; }