矩阵链乘

题目：

      输入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 矩阵链乘

用map的矩阵链乘

 

拓展下：

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

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

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