西乡网站建设公司,网站代码下载,做数据新闻的网站有哪些方面,视频做网站背景Powered by:NEFU AB-IN
Link 文章目录 HJ70 矩阵乘法计算量估算题意思路代码 HJ70 矩阵乘法计算量估算 题意 矩阵乘法的运算量与矩阵乘法的顺序强相关。 例如#xff1a; A是一个5010的矩阵#xff0c;B是1020的矩阵#xff0c;C是205的矩阵 计算ABC有两种顺序#xff1a;…Powered by:NEFU AB-IN
Link 文章目录 HJ70 矩阵乘法计算量估算题意思路代码 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 pairint, 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_mapchar, 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;stackPII 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;
}
