华为OJ矩阵乘法计算量估算

r囧r小猫 2022-06-17 08:48 179阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px">矩阵乘法的运算量与矩阵乘法的顺序强相关。 例如：&nbsp;&nbsp;&nbsp;&nbsp;A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵&nbsp;计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。&nbsp;编写程序计算不同的计算顺序需要进行的乘法次数&nbsp;&nbsp;&nbsp;&nbsp;</pre> </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 字符串</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则 3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//矩阵个数n&nbsp; 50&nbsp;10&nbsp;&nbsp;&nbsp;//矩阵A的行数50，列数10 10&nbsp;20&nbsp;&nbsp;&nbsp;//矩阵B的行数10，列数20 20&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;//矩阵C的行数20，列数5 (A(BC))&nbsp;//矩阵从A开始命名，A、B、C、D...以此类推，通过括号表示运算顺序 &nbsp; </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 输出需要进行的乘法次数 </td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 3 50 10 10 20 20 5 (A(BC))</td> 
 </tr> 
 <tr style=""> 
 <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
 <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 3500</td> 
 </tr> 
 </tbody> 
</table>

#include <iostream> 
 #include <vector>
 #include <string>
 #include <stack>
 #include <map>
 #include <algorithm>
 
 using namespace std;
 
 struct matrix
 {
 	int row;
 	int col;
 };
 
 void main()
 {
 	vector<matrix> vec;
 	stack<matrix> sta;
 	int n;
 	cin >> n;
 	for (int i = 0; i < n; i++)
 	{
 		matrix tmp;
 		cin >> tmp.row >> tmp.col;
 		vec.push_back(tmp);
 	}
 	string str;
 	cin >> str;
 	int result = 0;
 	for (int i = 0; i < str.length(); i++)
 	{
 		if (str[i] >= 'A'&&str[i] <= 'Z')
 		{
 			int index = str[i] - 'A';
 			sta.push(vec[index]);
 		}
 		else if (str[i] == ')')
 		{
 			matrix value1 = sta.top();
 			sta.pop();
 			matrix value2 = sta.top();
 			sta.pop();
 			matrix value3;
 			value3.row = value2.row;
 			value3.col = value1.col;
 			sta.push(value3);
 			result += value2.row*value2.col*value1.col;
 		}
 	}
 	cout << result;
 }