当前位置:网站首页>[exercise-3] (UVA 442) matrix chain multiplication
[exercise-3] (UVA 442) matrix chain multiplication
2022-07-06 15:56:00 【Flame car】
Translate directly :
Input n Dimensions of matrices and expressions of matrix chain multiplication , Output the number of multiplications . If multiplication doesn't work , The output error. Jiading A yes mn Matrix ,B yes np Matrix , that AB yes mp Matrix , The number of multiplications is mn*p. If A The number of columns is not equal to B The number of rows , Then multiplication cannot be performed .
for example ,A yes 50 * 10 Of ,B yes 10 * 20 Of ,C yes 20 * 5 Of , be (A(BC)) Is multiplied by 10 * 20 * 5(BC The number of multiplications ) + 50 *10 * 5((A(BC)) The number of multiplications ) = 3500.
AC Code :
#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;
}
}
Ideas :
① Use a structure to store two values of each letter .
② Stack the structure
③ encounter ‘(’ Ignore , encounter ’)' Operate once when .
④ Content of operation : Take out the first two elements of the stack for matrix chain multiplication ( Note that the first one is the back one ,AB Perform matrix chain multiplication , Stack pops up first B Pop up after A), Put the newly obtained element on the stack .
⑤ If matrix chain multiplication cannot be performed, mark and exit .
I didn't understand at first , Want to put characters char Put it in the stack , But in this way Put the newly obtained elements on the stack It's very troublesome , If you put the structure directly into the stack, it can be easily implemented .
Here you can write a Constructors , Directly initialize the definition structure (C++ I learned it in school ), In that case, you can define one less tmp Structure .
边栏推荐
- Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
- 最全编程语言在线 API 文档
- TCP的三次握手与四次挥手
- 入门C语言基础问答
- Information security - threat detection - detailed design of NAT log access threat detection platform
- Interesting drink
- Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
- Penetration test (3) -- Metasploit framework (MSF)
- 【练习4-1】Cake Distribution(分配蛋糕)
- Information security - threat detection engine - common rule engine base performance comparison
猜你喜欢
STM32 learning record: LED light flashes (register version)
Nodejs+vue网上鲜花店销售信息系统express+mysql
C语言学习笔记
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
Borg Maze (BFS+最小生成树)(解题报告)
力扣刷题记录
C语言必背代码大全
随机推荐
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
Accounting regulations and professional ethics [4]
Information security - Analysis of security orchestration automation and response (soar) technology
China earth moving machinery market trend report, technical dynamic innovation and market forecast
China's salt water membrane market trend report, technological innovation and market forecast
MySQL授予用户指定内容的操作权限
Cost accounting [13]
STM32 learning record: LED light flashes (register version)
E. Breaking the Wall
Opencv learning log 31 -- background difference
【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
Learning record: Tim - Basic timer
Cost accounting [23]
STM32 learning record: play with keys to control buzzer and led
F - Birthday Cake(山东省赛)
Research Report on market supply and demand and strategy of geosynthetics industry in China
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
JS调用摄像头
Record of brushing questions with force deduction -- complete knapsack problem (I)
Opencv learning log 13 corrosion, expansion, opening and closing operations