当前位置:网站首页>【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
2022-07-06 09:26:00 【火焰车】
直接翻译:
输入n个矩阵的维度和一些矩阵链乘的表达式,输出乘法的次数。如果乘法无法进行,则输出error。嘉定A是mn的矩阵,B是np的矩阵,那么AB是mp的矩阵,乘法次数为mn*p。如果A的列数不等于B的行数,则乘法无法进行。
例如,A是50 * 10的,B是10 * 20的,C是20 * 5的,则(A(BC))的乘法次数为10 * 20 * 5(BC的乘法次数) + 50 *10 * 5((A(BC))的乘法次数) = 3500.
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
struct node{
int x;
int y;
}a[26];
int main()
{
int n;
char ch;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ch;
cin>>a[ch-'A'].x;
cin>>a[ch-'A'].y;
}
string s;
while(cin>>s)
{
stack<node> st;
int f=1,ans=0;
int len = s.size();
if(len == 0 )
{
cout<<0<<endl;
continue;
}
for(int i=0;i<len;i++)
{
if(s[i]>='A' && s[i]<='Z')
st.push(a[s[i]-'A']);
else if(s[i]==')')
{
node x2 = st.top();st.pop();
node x1 = st.top();st.pop();
if(x1.y != x2.x){
f = 0;
break;
}
ans+=x1.x*x1.y*x2.y;
node tmp;
tmp.x=x1.x,tmp.y=x2.y;
st.push(tmp);
}
}
if(f)
cout<<ans<<endl;
else
cout<<"error"<<endl;
}
}
思路:
①用结构体存放每个字母的两个值。
②用栈来存放结构体
③遇到‘(’时忽略,遇到’)'时进行一次操作。
④操作的内容:把栈的前两个元素拿出来进行矩阵链乘(注意先拿出来的是后面的,AB进行矩阵链乘,栈首先弹出B后弹出A),把新得到的元素放进栈。
⑤如果不能进行矩阵链乘则标记并退出。
一开始没想明白,想要把字符char放进栈里,但是这样的话实现 把新得到的元素进栈 是挺麻烦的,如果是直接放进把结构体放进栈里就可以很容易的实现了。
在这里可以在结构体中写一个构造函数,直接初始化定义结构体(C++里学过),那样的话可以少定义一个tmp结构体。
边栏推荐
- MATLAB综合练习:信号与系统中的应用
- Report on the market trend, technological innovation and market forecast of printing and decorative paper in China
- cs零基础入门学习记录
- 想应聘程序员,您的简历就该这样写【精华总结】
- csapp shell lab
- China's PCB connector market trend report, technological innovation and market forecast
- Cost accounting [17]
- Accounting regulations and professional ethics [1]
- Opencv learning log 30 -- histogram equalization
- Accounting regulations and professional ethics [5]
猜你喜欢
随机推荐
Cost accounting [13]
Opencv learning log 31 -- background difference
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
STM32学习记录:玩转按键控制蜂鸣器和LED
Opencv learning log 19 skin grinding
Cost accounting [17]
FSM and I2C experiment report
基于web的照片数码冲印网站
力扣刷题记录
ucorelab4
Matlab comprehensive exercise: application in signal and system
Cost accounting [14]
Flink 使用之 CEP
Cost accounting [24]
Shell脚本编程
动态规划前路径问题优化方式
Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
Find 3-friendly Integers
Gartner:关于零信任网络访问最佳实践的五个建议