FZU 1061 矩阵连乘

ShenduCC

发布于 2018-04-26 17:22:52

8210

发布于 2018-04-26 17:22:52

文章被收录于专栏：算法修养

Problem 1061 矩阵连乘

Accept: 445 Submit: 1699 Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

给定n个矩阵{A1,A2,...,An}，考察这n个矩阵的连乘积A1A2...An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。

矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3个矩阵{A1,A2,A3}连乘积的例子。设这3个矩阵的维数分别为10*100，100*5，和5*50。若按(A1A2)A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50 = 7500。若按A1(A2A3)计算，则总共需要100*5*50+10*100*50 = 75000次数乘。

现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。

Input

输入数据由多组数据组成。每组数据格式如下：第一行是一个整数n (1≤n≤26)，表示矩阵的个数。接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1<a,b<100。第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。

Output

对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。

Sample Input

3A 10 100B 100 5C 5 50A(BC)

Sample Output

75000

栈应用

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>

using namespace std;
struct Node
{
  int a;
  int b;
}e[105];
map<char,int> m;

char c;
char d[2005];
Node s[2005];
Node s2[2005];
int top2;
int top;
long long int sum;
bool ans;
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		ans=true;
		getchar();
		for(int i=1;i<=n;i++)
		{
			scanf("%c ",&c);
			m[c]=i;
			scanf("%d%d",&e[i].a,&e[i].b);
			getchar();
		}
		scanf("%s",d);
		int len=strlen(d);
		top=-1;top2=-1;
		for(int i=0;i<len;i++)
		{
			if(d[i]=='(')
			{
				Node term;
				term.a=0;term.b=0;
				s[++top]=term;
			}
			else if(d[i]==')')
			{
				top2=-1;
                while(s[top].a!=0&&top!=-1)
				{
					s2[++top2]=s[top];
					top--;
				}
				
				if(top2==0)
                    s[top]=s2[top2];
				else
				{
					if(s2[top2].b!=s2[top2-1].a)
					ans=false;
                sum+=s2[top2].a*s2[top2].b*s2[top2-1].b;
				Node temp;temp.a=s2[top2].a;temp.b=s2[top2-1].b;
				top2-=2;
				while(top2!=-1)
				{
					if(temp.b!=s2[top2].a)
						ans=false;
                  sum+=temp.a*temp.b*s2[top2].b;
				  temp.a=temp.a;temp.b=s2[top2].b;
				  top2--;
				}
				top--;
				s[++top]=temp;
				}
			}
			else
              s[++top]=e[m[d[i]]];
		}
        top2=-1;
		while(top!=-1)
		{
            s2[++top2]=s[top];
				top--;
		}
        if(top2==0)
		{
           if(!ans)
			printf("error\n");
		   else
			printf("%lld\n",sum);
		}
		else
		{
		sum+=s2[top2].a*s2[top2].b*s2[top2-1].b;
		if(s2[top2].b!=s2[top2-1].a)
					ans=false;
		Node temp;temp.a=s2[top2].a;temp.b=s2[top2-1].b;
		top2-=2;
		while(top2!=-1)
		{
			if(temp.b!=s2[top2].a)
				ans=false;
            sum+=temp.a*temp.b*s2[top2].b;
			temp.a=temp.a;temp.b=s2[top2].b;
			top2--;
		}
		if(!ans)
			printf("error\n");
		else
			printf("%lld\n",sum);
		}
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-05-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法