矩阵链乘

柔光的暖阳◎ 2022-05-10 08:03 179阅读 0赞

## 题目： ##

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

例如，A是50\*10的，B是10\*20的，C是20\*5的，则（A(BC)）的乘法次数为10\*20\*5（BC的乘法次数）+50\*10\*5=3500.

输入，输出见example。

## Sample Input ##

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

## Sample Output ##

0
    0
    0
    error
    10000
    error
    3500
    15000
    40500
    47500
    15125

## 分析： ##

这道题目需要注意的是，先取出的是矩阵2，后取出的是矩阵1。（这个错误把我头都查大了）

关于字母和结构体的映射，代码用了“桶”的思想。后面的参考文章中用了map映射，很巧妙的建立新的关键字。

代码：

#include<iostream>
    #include<stack>
    #include<string>
    #include<cstring>
    #include<cctype>
    using namespace std;
    
    struct matrix
    {
    	int a,b;
    	matrix(int a=0,int b=0):a(a),b(b){}
    }m[26];
    
    int main()
    {
    	int i,n;
    	char cha;
    	int a,b;
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    		getchar();
    		cin>>cha;	
    		cin>>a>>b;
    		m[cha-'A'].a=a;//桶的思想 
    		m[cha-'A'].b=b;
    	}
    	//cout<<m[0].a<<" "<<m[0].b <<endl;
    	//cout<<m[1].a<<" "<<m[1].b <<endl;
    	
    	string expr;
    	int len;
    	stack<matrix> s;
    	matrix matx1,matx2,matxtmp;
    	while(cin>>expr)
    	{
    		int ans=0;
    		len=expr.length();
    		//cout<<"len:"<<len<<endl; 
    		for(i=0;i<len;i++)
    		{
    			cha=expr[i];
    			if(isalpha(cha))
    				s.push(m[cha-'A']);
    			else if(expr[i]==')')
    			{
    				matx2=s.top();s.pop();
    				matx1=s.top();s.pop();//注意是先matx2，后matx1 
    				//cout<<"matx1.b:"<<matx1.b<<"matx2.a:"<< matx2.a<<endl;
    				if(matx1.b==matx2.a)
    				{
    					ans=ans+matx1.a*matx1.b*matx2.b;
    					matxtmp.a=matx1.a;
    					matxtmp.b=matx2.b;
    					s.push(matxtmp);
    				}
    				else
    				{
    					cout<<"error"<<endl;
    					break;
    				}
    			}//cout<<"*"<<cha<<"*"<<i; 	
    		}
    		if(i==len)
    			cout<<ans<<endl; 
    	} 
    	return 0;
    }

参考文章：

[UVa442 矩阵链乘][UVa442]

[用map的矩阵链乘][map]

拓展下：

1、如果给出一行没有加括号的字符串（eg:ABC），如何加括号使得计算次数最少？

2、如果题目给的ABC，没有按照顺序给出，比如是BAC，如何确定顺序，增加括号，使得能正确计算，并且次数最少？

上面的问题不想想了，脑壳疼：[矩阵连乘-动态规划][-]

[UVa442]: https://blog.csdn.net/yejin_tianming/article/details/82531285
[map]: https://www.cnblogs.com/pgzhang/p/9385732.html
[-]: https://blog.csdn.net/huzhigenlaohu/article/details/52182944