首页 > 代码库 > UVA - 442 Matrix Chain Multiplication
UVA - 442 Matrix Chain Multiplication
点击打开链接
题目意思是求矩阵相乘的运算次数,
设A size为n*s,B size为s*m
那么A*B运算量为n*m*s.
那么A*B运算量为n*m*s.
注意括号里面的优先级,并且依次累加即可,并且没有不合法的序列。
思路是先对输入的n个矩阵编号按照字典序排序,因为每次两个矩阵相乘会得到一个新的矩阵,编号可以设置成在n的编号加1,并且重新压入栈中。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <string> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> //#include <stack> #include <map> #include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long #define inf 0x7f7f7f7f #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define lowbit(x) (x)&(-x) #define Read() freopen("a.txt", "r", stdin) #define Write() freopen("dout.txt", "w", stdout); #define N 100005 using namespace std; struct node { int a,b; char c; }p[30]; bool cmp(node x,node y) { return x.c<y.c; } char s[10000],stack[10000]; //栈 int main() { //Read(); int n,i,j,k; while(~scanf("%d",&n)) { getchar(); for(i=0;i<n;i++) { scanf("%c %d %d",&p[i].c,&p[i].a,&p[i].b); getchar(); } sort(p,p+n,cmp); while(gets(s)) { int l=strlen(s),top,num=0; for(i=0,top=0;i<l;i++) { if(s[i]=='(') stack[top++]=s[i]; else if(s[i]>='A'&&s[i]<='Z') stack[top++]=s[i]; //把不是 右括号的都压入栈 else if(s[i]==')') { for(j=0;j<n;j++) if(stack[top-2]==p[j].c) break; for(k=0;k<n;k++) if(stack[top-1]==p[k].c) break; //找出 编号 if(p[j].b!=p[k].a) break; //如果矩阵不能相乘 就跳出 num+=p[j].a*p[j].b*p[k].b; // printf("%d\n",num); p[n].a=p[j].a;p[n].b=p[k].b;p[n].c=p[n-1].c+1; //生成一个新的矩阵 stack[top-3]=p[n].c;top-=2; //退栈 n++; } } if(i<l) printf("error\n"); else printf("%d\n",num); } } return 0; }
UVA - 442 Matrix Chain Multiplication
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。