UVA 442：Matrix Chain Multiplication 数据结构专题

UVA 442：Matrix Chain Multiplication 数据结构专题2014-10-06 shuangde800 题目链接：http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=383

题目类型：数据结构，链表

样例输入：

9A 50 10B 10 20C 20 5D 30 35E 35 15F 15 5G 5 10H 10 20I 20 25ABC（AA）（AB）（AC）（A（BC））（（AB）C）（（（（（DE）F）G）H）I）（D（E（F（G（HI）））））（（D（EF））（（GH）I））

样例输出：

000error10000error350015000405004750015125

题目大意：

给出一系列的矩阵，给他们取名A ，B…… 以及它们的行数和列数。给完后，给出一系列的表达式，然后要求求出按这些表达式进行计算，会有多少次乘法步骤。

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45537.htm

解体思路：

这题和括号匹配那题很像。关键的步骤是计算矩阵乘法次数的这个过程。

#include<cstdio>#include<cctype>#include<cstring>#include<cstdlib>#include<stack>using namespace std;int sum,n;int mat[30][2];int arr[30],prev[30], next[30];char str[1000];void solve（）{// 如过只有一个矩阵，那么直接输出结果0if（strlen（str）==1 && isupper（str[0]））{printf（"0
"）;}else{char copyMat[30][2];int i,j;// 复制一个数组进行操作。 因为后面的操作需要对这些矩阵进行修改for（i=0; i<n; ++i）{copyMat[i][0] = mat[i][0];copyMat[i][1] = mat[i][1];}sum=0;stack<char>st; for（i=0; i<strlen（str）; ++i）{if（str[i]=="（" || isupper（str[i]））st.push（str[i]）;else if（str[i]=="）"）{stack<char>temp;// 当碰到‘）’时，把栈中的矩阵全都取出来进行计算 while（isupper（st.top（）））{temp.push（st.top（））;st.pop（）;}// 把"（"也弹出st.pop（）;char ex;// 取出第一个矩阵（在原表达式中是最左边的一个）if（！temp.empty（））{ex=temp.top（）;temp.pop（）;}while（！temp.empty（））{char multi = temp.top（）;temp.pop（）;// 如果左边矩阵的列数和右边矩阵的函数不同，则直接输出 errorif（copyMat[ex-"A"][1] ！= copyMat[multi-"A"][0]）{printf（"error
"）;return ;}// 计算相乘次数，加上sum += copyMat[ex-"A"][0]*copyMat[multi-"A"][0]*copyMat[multi-"A"][1];// 相乘后得到一个新矩阵，更新尺寸copyMat[ex-"A"][1] = copyMat[multi-"A"][1];}st.push（ex）;}}printf（"%d
",sum）;}}int main（）{freopen（"input.txt", "r",stdin）;char ch;inti, j;scanf（"%d%*c", &n）;for（i=0; i<n; ++i）{scanf（"%c %d %d%*c",&ch,&mat[i][0],&mat[i][1]）;}while（gets（str））{solve（）;}return 0;}