Matrix Chain Multiplication 矩阵链乘 UVA 442

╰半橙微兮° 2024-02-17 18:49 62阅读 0赞

解题思路：首先解决如何保存输入字母所对应的两个值，通过定义结构体数组nt\[0\]表示字符'A',以此类推；然后通过通过栈来储存输入的字母，遇到")"时出栈两个元素做运算（"(" ")"不入栈）。

1.  \#include<cstdio>
2.  \#include<stack>
3.  \#include<iostream>
4.  \#include<string>
5.  using namespace std;
6.  struct note\{ 
7.   int a,b;
8.   note (int a1=0,int b1=0):a(a1),b(b1)\{\}
9.  \}nt\[30\];
10. stack<note>st;
11. int main()\{ 
12.  int n;
13.  scanf("%d",&n);
14.  for(int i=0;i<n;i++)
15.  \{ 
16.  getchar(); //吃掉换行，否则会错 
17.  char ch;
18.  scanf("%c",&ch);
19.  int t=ch-'A';
20.  scanf("%d%d",&nt\[t\].a,&nt\[t\].b);
21.  \}
22.  string str;
23.  while(cin>>str)\{ 
24.  int flag=1;
25.  int sum=0;
26.  for(int i=0;i<str.length();i++)\{ 
27.  if(isalpha(str\[i\]))st.push(nt\[(str\[i\]-'A')\]);
28.  else if(str\[i\]==')')\{ 
29.  note n1=st.top();st.pop();
30.  note n2=st.top();st.pop();
31.  if(n2.b==n1.a)\{ 
32.  sum+=n2.a\*n2.b\*n1.b;
33.  st.push(note(n2.a,n1.b));
34.  \}
35.  else \{ 
36.  flag=0;
37.  break;
38.  \}
39.  \}
40.  \}
41.  if(flag)printf("%d\\n",sum);
42.  else printf("error\\n");
43.  \}
44.  return 0;
45. \}

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关 Matrix Chain Multiplication 矩阵链乘 UVA 442

解题思路：首先解决如何保存输入字母所对应的两个值，通过定义结构体数组nt\[0\]表示字符'A',以此类推；然后通过通过栈来储存输入的字母，遇到")"时出栈两个元素做运算（"(

╰半橙微兮°/ 2024年02月17日 18:49/ 0 赞/ 63 阅读

相关洛谷-UVA442 矩阵链乘 Matrix Chain Multiplication

题目描述 [PDF][] ![format_png][] 输入格式 ![format_png 1][] 输出格式 ![format_png 2][]

电玩女神/ 2023年05月29日 09:17/ 0 赞/ 21 阅读

相关矩阵链乘（Matrix Chain Multiplication）

题目描述假设你必须评估一种表达形如 ABCDE，其中 A,B,C,D,E是矩阵。既然矩阵乘法是关联的，那么乘法的顺序是任意的。然而，链乘的元素数量必须由你选择的赋值顺

拼搏现实的明天。/ 2022年12月01日 01:21/ 0 赞/ 134 阅读

相关 UVA11082 Matrix Decompressing(矩阵解压) 最大流

题意：对于一个R行C列的正整数矩阵，(1<=R,C<=20),设a\[i\]为前i行所有元素之和，b\[i\]为前i列所有元素之和，已知道R，C，和数组a，b，找一个满足条件

末蓝、/ 2022年10月02日 11:46/ 0 赞/ 166 阅读

相关【日常学习】【栈】【表达式求值】Uva442 - Matrix Chain Multiplication题解

之前一直没有写过栈的典型程序，这里写一个。这个程序完全是我独立写出来的，我还没有看ruka上的标程，或许会有些不同。题目来源：University of Ulm Local

￡神魔★判官ぃ/ 2022年08月07日 02:00/ 0 赞/ 21 阅读

相关 UVA 10895——Matrix Transpose

题意：给定一个矩阵（每一行有几个非0的数据，对应的位置以及数值），输出这个矩阵的转置矩阵。思路：直接模拟，用两个vector，一个维护数值，另外一个维护行号。注意

Myth丶恋晨/ 2022年07月29日 09:26/ 0 赞/ 136 阅读

相关【矩阵幂的和+矩阵快速幂】Power of Matrix UVA - 11149

Think: 1知识点：矩阵幂的和+矩阵快速幂 2题意：输入矩阵A，求A^1 + A^2 + … + A^(n) 3题意分析：（1）：倍增法求矩阵幂的和，eg

本是古典何须时尚/ 2022年06月07日 06:09/ 0 赞/ 210 阅读

相关矩阵链乘

题目：输入n个矩阵的维度和一些矩阵的链乘表达式，输出乘法的次数。如果乘法无法进行，输出error。假定A是m\n矩阵，B是n\p的矩阵，那么A\B是m\p的

柔光的暖阳◎/ 2022年05月10日 08:03/ 0 赞/ 187 阅读

相关 UVA11992 Fast Matrix Operations 快速矩阵操作（线段树）

题意：对矩阵有三种操作，第一是让矩阵的每个元素加上某个数，第二是让矩阵得每个元素变成某个数，第三是输出某个子矩阵的数字总和，最大值和最小值。开始时，矩阵得每个元素为0.

旧城等待，/ 2021年12月11日 09:25/ 0 赞/ 150 阅读

相关 POJ2246-Matrix Chain Multiplication

[http://poj.org/problem?id=2246][http_poj.org_problem_id_2246] 矩阵相乘，不明白方法的同学去看一下线性代数~~~

淡淡的烟草味﹌/ 2021年11月26日 13:18/ 0 赞/ 206 阅读