UVA-442 Matrix Chain Multiplication

本文主要是介绍UVA-442 Matrix Chain Multiplication，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/UVA-442

题意：输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。若乘法无法进行，输出error。假定A是m*n矩阵，B是n*p矩阵，那么AB是n*p矩阵，乘法次数为m*n*p。若A的列数不等于B的列数，则乘法无法进行。

分析：用栈即可求出结果，遇到字母入栈，遇到右括号出栈并计算，结果入栈。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
const int MAXN=30;struct rec {int a,b;
} m[MAXN];int main() {//freopen("in.txt","r",stdin);int n;cin>>n;for(int i=0; i<n; i++) {char c;cin>>c;int k=c-'A';cin>>m[k].a>>m[k].b;}string expr;while(cin>>expr) {int ans=0;stack<rec> s;bool error=false;for(int i=0; i<expr.size(); i++) {if(isalpha(expr[i])) s.push(m[expr[i]-'A']);else if(expr[i]==')') {rec m1=s.top();s.pop();rec m2=s.top();s.pop();if(m1.a!=m2.b) {error=true;break;}ans+=m2.a*m2.b*m1.b;m2.b=m1.b;s.push(m2);}}if(!error) cout<<ans<<endl;else  cout<<"error"<<endl;}return 0;
}

这篇关于UVA-442 Matrix Chain Multiplication的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---