当前位置:网站首页>【练习-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结构体。
边栏推荐
- Cost accounting [23]
- Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
- 0-1 knapsack problem (I)
- B - 代码派对(女生赛)
- Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
- Cost accounting [21]
- cs零基础入门学习记录
- 学习记录:USART—串口通讯
- Learning records: serial communication and solutions to errors encountered
- Perinatal Software Industry Research Report - market status analysis and development prospect forecast
猜你喜欢
随机推荐
Cost accounting [20]
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
Research Report of peripheral venous catheter (pivc) industry - market status analysis and development prospect prediction
Cost accounting [22]
E. Breaking the Wall
Market trend report, technical innovation and market forecast of geosynthetic clay liner in China
Nodejs+vue网上鲜花店销售信息系统express+mysql
ucore lab7
信息安全-威胁检测引擎-常见规则引擎底座性能比较
Accounting regulations and professional ethics [2]
JS调用摄像头
Market trend report, technical innovation and market forecast of Chinese hospital respiratory humidification equipment
差分(一维,二维,三维) 蓝桥杯三体攻击
Opencv learning log 30 -- histogram equalization
学习记录:使用STM32外部输入中断
ucore lab5
JS --- BOM details of JS (V)
STM32学习记录:玩转按键控制蜂鸣器和LED
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
区间和------离散化