【UVA No. 442】 矩阵链乘 Matrix Chain Multiplication

【UVA No. 442】 矩阵链乘 Matrix Chain Multiplication

洛谷题目地址

【题意】

假设你必须评估一种表达式，比如 A × B × C × D × E ，其中 A 、 B 、 C 、 D 、 E 是矩阵。

既然矩阵乘法满足结合率，那么乘法的顺序是任意的。矩阵连乘的乘法次数由相乘的顺序决定。例如， A 、 B 、 C 分别是50×10、10×20和20×5的矩阵。 现在有两种方案计算 A × B × C ，即( A × B )× C 和 A×( B × C )。第1种要进行15 000次乘法运算，而第2种只进行3 500次乘法运算。

写程序，计算给定矩阵表达式需要进行多少次乘法运算。

【输入输出】

输入：

输入包含矩阵和表达式两部分。在第1部分，第1行包含一个整数n （1≤n ≤26），代表矩阵的个数；接下来的n 行，每行都包
含了一个大写字母来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。第2部分是一个矩阵或矩阵表达式。

输出：

对于每一个表达式，如果乘法无法进行，则输出“Error”，否则输出所需的乘法运算次数。

【样例】

【思路分析】

[什么是矩阵可乘]

如果第1个矩阵的列等于第2个矩阵的行，那么这两个矩阵是可乘的。

[矩阵相乘后的结果是什么]

两个矩阵相乘的结果矩阵，其行、列分别等于第1个矩阵的行、第2个矩阵的列。

如果有多个矩阵相乘

多个矩阵相乘的结果矩阵，其行、列分别等于第1个矩阵的行、最后1个矩阵的列。而且无论矩阵的计算次序如何，都不影响它们的结果矩阵。

[两个矩阵相乘需要进行多少次乘法运算]

例如两个矩阵 A 3×2 、 B 2×4 相乘，结果为 C 3×4

1. A 矩阵第1行第1个数× B 矩阵第1列第1个数：1×2。
2. A 矩阵第1行第2个数× B 矩阵第1列第2个数：2×3。
3. 将两者相加并存放在 C 矩阵第1行第1列：1×2+2×3。
4. A 矩阵第1行第1个数× B 矩阵第2列第1个数：1×4。
5. A 矩阵第1行第2个数× B 矩阵第2列第2个数：2×6。
6. 将两者相加并存放在 C 矩阵第1行第2列：1×4+2×6。
7. A 矩阵第1行第1个数× B 矩阵第3列第1个数：1×5。
8. A 矩阵第1行第2个数× B 矩阵第3列第2个数：2×9。
9. 将两者相加并存放在 C 矩阵第1行第3列：1×5+2×9。
10. A 矩阵第1行第1个数× B 矩阵第4列第1个数：1×8。
11. A 矩阵第1行第2个数× B 矩阵第4列第2个数：2×10。
12. 将两者相加并存放在 C 矩阵第1行第4列：1×8+2×10。

可以看出，结果矩阵中的每个元素都执行了两次乘法运算，那么在结果矩阵中有3×4=12个数，共需要执行2×3×4=24次乘法运算，两个矩阵A 3×2 、A 2×4 相乘执行乘法运算的次数为3×2×4。

因此，Am × n、An × k 相乘执行乘法运算的次数为m ×n ×k 。

【算法设计】

1. 首先将矩阵及行列值存储在数组中。
2. 读入一行矩阵表达式。
3. 到矩阵名称时入栈，遇到右括号时出栈。两个矩阵m 2 、m，如果m 1 的列不等于m 2 的行，则矩阵不可乘，标记error=true并退出循环，否则计算乘法运算的次数，并将两个矩阵相乘后的结果矩阵入栈。
4. 如果error=true，则输出“error”，否则输出乘法运算的次数。

【完美图解】

① 以输入样例(A(BC))为例，其中 A 50 10； B 10 20； C 20 5，字母表示矩阵名，后两个数字分别表示该矩阵的行和列。遇到左括号什么也不做，遇到矩阵名则入栈，首先 ABC 入栈

② 遇到右括号时出栈。两个矩阵 C 、 B ， B 10 20； C 20 5； B 的列等于 C 的行，两个矩阵是可乘的，乘法运算的次数为
10×20×5=1000，结果矩阵 X 的行 为 B 的行10， X 的列为 C 的列5，即 X 10 5，将结果矩阵入栈，如下图所示。

③ 遇到右括号时出栈。两个矩阵 X 、 A ， A 50 10； X 10 5； A 的列等于X的行，两个矩阵是可乘的，乘法运算的次数为
50×10×5=2500，累计次数为1000+2500=3500，结果矩阵 Y 的行为 A的行50， Y 的列为 X 的列5，即 Y 50 5，将结果矩阵入栈，如下图所示。

④ 表达式读入完毕，输出结果3500。

【算法实现】

#include
#include
#include
#include

using namespace std;
const int maxsize=26 + 10;

struct Matrix{//矩阵结构体 
	int a,b;//矩阵行列 
	Matrix(int a=0,int b=0):a(a),b(b){} //构造方法 
}m[maxsize];

stack<Matrix> s;

int main(){
	
    int n;
    char c;
    string str;
	cin>>n;
    for(int i=0;i<n;i++){
    	cin>>c;
    	int k=c-'A';//转换为整数 
    	cin>>m[k].a>>m[k].b;//输入矩阵的行列 
	}
	
    while(cin>>str){
    	
		int len=str.length();
		bool error=false;
		int ans=0;
		
		for(int i=0;i<len;i++){
			
			if(isalpha(str[i]))
				s.push(m[str[i]-'A']);
				
			else if(str[i]==')'){
				
				Matrix m2=s.top();s.pop();
				Matrix m1=s.top();s.pop();
				
				if(m1.b!=m2.a){ //不能相乘 
					error=true;
					break;
				}
				ans+=m1.a*m1.b*m2.b;
				s.push(Matrix(m1.a,m2.b));
			}
		}
		
		if(error){
			cout << "error" << endl;		
		}
	    else{
	    	cout << ans << endl;
		}	
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

还是跑一下样例

OK