題目鏈接 https://cn.vjudge.net/problem/UVA-442

【題意】
輸入n個矩陣的維度和一些矩陣鏈乘表達式，輸出乘法次數。如果乘法無法執行，輸出error。假定A是m×n矩陣，B是n×p矩陣，則A×B的結果是一個m×p矩陣，乘法次數是m×n×p，當左邊矩陣的列不等于右邊矩陣的行時，乘法就無法進行。保證輸入合法并且每個括號里面只包含兩個矩陣。

【思路】
用一個棧來模擬計算過程，因為輸入保證合法，所以不需要把括號壓入棧中。只要遇到的是矩陣就把它壓入棧中，當碰到右括號的時候，把棧的頂端的兩個矩陣取出，然后計算乘法次數，同時把得到的矩陣再壓回棧中。

#include<bits/stdc++.h> using namespace std;const int maxn=30;struct node{int r,c;node(int rr=0,int cc=0):r(rr),c(cc){} };int n; node rec[maxn];int main(){cin.tie(0);ios_base::sync_with_stdio(0);cin>>n;while(n--){char ch;int r,c;cin>>ch>>r>>c;rec[ch-'A']=node(r,c);}string s;while(cin>>s){stack<node> st;int ans=0;bool ok=true;for(int i=0;i<s.length();++i){if('A'<=s[i] && s[i]<='Z') st.push(rec[s[i]-'A']);else if(')'==s[i]) {node x=st.top();st.pop();node y=st.top();st.pop();if(y.c!=x.r) {ok=false;break;}ans+=y.r*y.c*x.c;st.push(node(y.r,x.c));}}if(ok) cout<<ans<<endl;else cout<<"error\n";}return 0; }

轉載于:https://www.cnblogs.com/wafish/p/10465336.html

總結

以上是生活随笔為你收集整理的Uva 442 - Matrix Chain Multiplication（模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。