C、矩阵相乘

题目描述

给定n个矩阵{A1,A2,…,An}，及m个矩阵连乘的表达式，判断每个矩阵连乘表达式是否满足矩阵乘法法则，如果满足，则计算矩阵的最小连乘次数，如果不满足输出“MengMengDa“。

输入

输入数据由多组数据组成（不超过10组样例）。每组数据格式如下：
第一行是2个整数n (1≤n≤26)和m(1≤m≤3)，表示矩阵的个数。
接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数r和c，分别表示该矩阵的行数和列数，其中1<r, c<100。
第n+1行到第n+m行，每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。

输出

对于每个矩阵连乘表达式，如果运算不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“MengMengDa”，否则输出最小矩阵连乘次数。
数据保证结果不超过1e9。

样例输入

3 2
A 10 100
B 5 50
C 100 5
ACB
ABC

样例输出

7500
MengMengDa

题解(动态规划问题)

#include <bits/stdc++.h>
#include<string> 
using namespace std;
struct node{
	char name;
	int r=0;
	int c=0;
}a[30];
		
int convert(char x, int n) {
	int i;
	for( i=0; i<n; i++) if(a[i].name == x) break;
	return i;
}
long int  MatrixCharin(int *p, int n,long  int m[][101])
{
	for(int i=0;i<=n;i++) m[i][i]=0; 
	for(int r=2; r<=n; r++) // r个矩阵相乘 
		for(int i=1; i<=n-r+1; i++)
		{
			int j = i+r-1; // 本循环的最后一个矩阵 
			m[i][j] = m[i][i] + m[i+1][j] + p[i-1]*p[i]*p[j]; // 假设最优划分位于i处 
			for(int k= i+1; k<j; k++) // 变化最优分割的位置， 逐一测试 
			{
				long int  t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if(t < m[i][j] ) m[i][j] = t; // 如果更优替换原位置 
			 } 
		}
	return m[1][n];
}
int main() {
	int m, n; 
	char str[3][101]; // 输入的矩阵字符串
	long int x[101][101];
	int p[3][101];
	int flag[3];
	while(cin>>n>>m){
		memset(str, 0, sizeof(' '));
		
         for(int i=0; i < n; i++) cin>>a[i].name>>a[i].r>>a[i].c;
         for(int i=0; i< m ; i++)
         {
         	cin>>str[i];
         	flag[i]=0;
         	for(int k=0; k< strlen(str[i]); k++)
         	{
         		if(k==0){
         			p[i][k] = a[convert(str[i][k], n)].r;
         			p[i][k+1] = a[convert(str[i][k], n)].c;
         		}
         		else {
         			if(p[i][k] == a[convert(str[i][k], n)].r){
        	 			p[i][k+1] = a[convert(str[i][k], n)].c;
         			}
        			else{
         				flag[i]=1;
         			}	
         		}
     		}
        }
         for(int i=0; i<m ; i++)
         {
        	if(flag[i] == 1){
         	cout<<"MengMengDa"<<endl;
         	}
         	else {
         		long int result = MatrixCharin(p[i], strlen(str[i]), x);
         		cout<<result<<endl;
         	}
         }
 	}
	return 0;
}