HJ70 矩阵乘法计算量估算

Powered by:NEFU AB-IN

Link

HJ70 矩阵乘法计算量估算

• 题意

  矩阵乘法的运算量与矩阵乘法的顺序强相关。
  例如：
  A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
  计算ABC有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。
  编写程序计算不同的计算顺序需要进行的乘法次数。

• 思路

  遇到括号问题，先想到用栈解决

  • 当遇到左括号，不用管
  • 当遇到右括号，根据题意，将数值弹出
  • 当遇到数值，压入栈即可

• 代码

  #include <bits/stdc++.h>
  #include <stack>
  #include <unordered_map>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int dp[N];signed main()
  {// freopen("Tests/input_1.txt", "r", stdin);IOS;int n;cin >> n;unordered_map<char, PII> mp;char A = 'A';for (int i = 1; i <= n; ++i){int x, y;cin >> x >> y;mp[A] = {x, y};A = A + 1;}int ans = 0;string s;cin >> s;stack<PII> st;for (auto i : s){if (i == '(')continue;else if (i == ')'){auto a = st.top();st.pop();auto b = st.top();st.pop();ans += a.first * a.second * b.first;st.push({b.first, a.second});}else{st.push({mp[i].first, mp[i].second});}}cout << ans;return 0;
  }