题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
这个题很奇怪,看来不用考虑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")