洛谷-UVA442 矩阵链乘 Matrix Chain Multiplication

电玩女神 2023-05-29 09:17 10阅读 0赞

## 题目描述 ##

[PDF][]

![format_png][]

## 输入格式 ##

![format_png 1][]

## 输出格式 ##

![format_png 2][]

## 题意翻译 ##

## 矩阵链乘 ##

### 题目描述 ###

假设你必须评估一种表达形如 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)。  
第一个要进行15000次基本乘法，而第二个只进行3500次。

你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。

### 输入格式 ###

输入包含两个部分：矩阵和表达式。 输入文件的第一行包含了一个整数 n(1 \\leq≤ n \\leq≤ 26), 代表矩阵的个数。接下来的n行每一行都包含了一个大写字母，说明矩阵的名称，以及两个整数，说明行与列的个数。  
第二个部分严格遵守以下的语法：

SecondPart = Line \{ Line \} <EOF> Line = Expression <CR> Expression = Matrix | "(" Expression Expression ")" Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

\#\#\#输出格式

对于每一个表达式，如果乘法无法进行就输出 " error "。否则就输出一行包含计算所需的乘法次数。

感谢@onceagain 提供翻译

## 输入输出样例 ##

**输入 \#1**复制

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))

**输出 \#1**复制

0
    0
    0
    error
    10000
    error
    3500
    15000
    40500
    47500
    15125

思路：栈中存放结构体，结构体记录mxn。

#include<bits/stdc++.h>
    using namespace std;
    struct HL{
    	int x,y;
    }HL[1000];
    
    //将字母转为数字唯一存储 
    stack<int> s;
    //乘的次数 
    int num=0;
    //是否为error 
    bool flag=true;
    //初始化矩阵 
    void init(){
    	int n;
    	char c;
    	cin>>n;
    	for(int i=0;i<n;i++){
    		cin>>c;
    		cin>>HL[c-'A'].x>>HL[c-'A'].y;
    	}
    }
    //合并 
    void add(int w,int x,int y){
    	HL[w].x=x;
    	HL[w].y=y;
    	s.push(w);
    }
    
    //取s栈中 两个字母做乘积 
    void count(){
    	//计算次数 
    	int w2=s.top();
    	int x2=HL[w2].x; 
    	int y2=HL[w2].y;
    	s.pop();
    	
    	int w1=s.top();
    	int x1=HL[w1].x; 
    	int y1=HL[w1].y; 
    	s.pop();
    	
    	if(y1!=x2){
    		flag=false; //为error
    	}
    	num=num+x1*y1*y2; //计算次数 
    	
    	//合并 
    	add(w1+w2+100,x1,y2);
    }
    
    
    
    int main(){
    	init();	
    	
    	string str;
    	while(cin>>str){
    		flag=true;
    		num=0;
    		for(int i=0;i<str.length();i++){
    			if(str[i]!=')'&&str[i]!='('){
    				int w=str[i]-'A';
    				s.push(w);	
    			}
    			if(str[i]==')'){
    				count();
    				//为error则不用在判断 
    				if(flag==false){
    					break;
    				}
    			}			
    		}
    		if(flag==false){
    			cout<<"error"<<endl;
    		}else{
    			cout<<num<<endl;
    		}
    		//清空栈(可要可不要):栈中存储了合并后不知名的数 
    		while(!s.empty()) s.pop(); 				
    	}
    	return 0;		
    }

我的答案：

#include <bits/stdc++.h>
    using namespace std;
    
    
    struct Node{
    	int x,y;
    }node[1000+5];
    
    int main(){
    	int n;
    	cin>>n; 
    	for(int i=0;i<n;i++){
    		char m;
    		cin>>m;
    		cin>>node[m-'A'].x;
    		cin>>node[m-'A'].y;
    	}	
    	
    	string s;
    	while(cin>>s){
    		stack<int> stac;
    		int temp=28;//存储中间矩阵的下标 
    		
    		
    		//是否为错误输入 
    		bool flag=true;
    		
    		//输入1个矩阵 
    		if(s.size()==1){
    			cout<<"0"<<endl;
    			continue;
    		}
    		//记录乘次数
    		int total=0; 
    		
    
    			//输入矩阵连乘 
    		for(int i=0;i<s.size();i++){ 
    			if(s[i]!=')'&&s[i]!='('){
    				stac.push(s[i]-'A');
    			}
    			
    			//进行连乘 
    			if(s[i]==')'){
    				int x2=node[stac.top()].x;
    				int y2=node[stac.top()].y;
    				stac.pop();
    				
    				int x1=node[stac.top()].x;	
    				int y1=node[stac.top()].y;			
    				stac.pop();
    				
    				if(y1!=x2){//不符合连乘条件 					
    					flag=false; 
    					break;
    				} else{
    					total=total+x1*y1*y2;
    					//保存中间节点
    					node[temp].x=x1;
    					node[temp].y=y2;
    					stac.push(temp++);					
    				}		
    			}
    		}
    		if(flag==true){
    			cout<<total<<endl;
    		}else{
    			cout<<"error"<<endl;
    		}
    	}
    	return 0; 
    }

示例：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70][]

[PDF]: https://uva.onlinejudge.org/external/4/p442.pdf
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ0Mi81NWVkNThkOThlNzRjOGNiNTRlOTI3ZjBjY2M0N2EwMTM2MjI2NGRkLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ0Mi9lYjA2ZjdhYmZlOTViODNiYjg2MjJjZjhjOTdmM2E2MWVlNTA5NWFhLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTQ0Mi8wYzZlNDQ0OThmOTk3Zjg5ZTUyNWExM2I3NjJmYjY3ZjQzNDgwZjQ0LnBuZw?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191105161505574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0,size_16,color_FFFFFF,t_70