首页 > 其他分享 >【UVA 442】Matrix Chain Multiplication 题解(栈)

【UVA 442】Matrix Chain Multiplication 题解(栈)

时间:2023-10-04 14:01:42浏览次数:50  
标签:ch 20 Matrix Chain int 题解 矩阵 表达式 乘法

假设您必须计算一个表达式,如ABCDE,其中A、B、C、D和E是矩阵。 由于矩阵乘法是关联的,所以执行乘法的顺序是任意的。 然而,所需的初等乘法的数量很大程度上取决于求值顺序 您可以选择。 例如,设A为5010矩阵,B为1020矩阵,C为205矩阵。有两个 计算ABC的不同策略,即(AB)C和A(B*C)。 第一个需要15000次基本乘法,但第二个只需要3500次。 你的工作是编写一个程序,确定所需的初等乘法的数量 对于给定的评估策略。

输入 输入由两部分组成:矩阵列表和表达式列表。 输入文件的第一行包含一个整数n(1≤n≤26),表示 第一部分中的矩阵。接下来的n行各包含一个大写字母,指定 矩阵和两个整数,指定矩阵的行数和列数。 输入文件的第二部分严格遵循以下语法(在EBNF中给出): SecondPart=行{行}<EOF> 直线=表达式 表达式=矩阵|“(“表达式表达式”)” 矩阵=“A”|“B”|“C”|…|“X”|“Y”|“Z” 输出 对于输入文件第二部分中的每个表达式,打印一行包含单词“error” 如果表达式的求值由于不匹配矩阵而导致错误。否则打印一个 包含计算表达式所需的基本乘法次数的行 由括号指定。

Sample Input 9 A 50 10 B 10 20 C 20 5 D 30 35 E 35 15 F 15 5 G 5 10 H 10 20 I 20 25 A B C (AA) (AB) (AC) (A(BC)) ((AB)C) (((((DE)F)G)H)I) (D(E(F(G(HI))))) ((D(EF))((GH)I)) Sample Output 0 0 0 error 10000 error 3500 15000 40500 47500 15125

思路

读入矩阵,用一个结构体数组储存矩阵,其中成员x为行,y为列。读入矩阵表达式,遇到右括号时让两个元素a和b出栈,如果a的列不等于b的行,矩阵不可乘,输出error;若矩阵可乘,将a和b按矩阵乘法规则相乘得到矩阵c,将c入栈,需要进行乘法运算的总数sum加上本次矩阵乘法需要进行乘法运算的次数,最后输出sum。

AC代码

#include <iostream>
#include <stack>
#include <sstream>
#define AUTHOR "HEX9CF"
using namespace std;

#define MAXN 100005;

int n;
struct S
{
    int x;
    int y;
} m[30];
stack<S> s;

S x(S a, S b)
{
    return S{a.x, b.y};
}

int xx(S a, S b)
{
    return a.x * a.y * b.y;
}

int getIndex(char ch)
{
    return ch - 'A';
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char ch;
        int t;
        cin >> ch;
        t = getIndex(ch);
        cin >> m[t].x >> m[t].y;
        // cout << t;
    }

    string str;
    while (cin >> str)
    {
        char ch;
        int sum = 0;
        bool err = false;
        stringstream ss(str);
        // cout << str << endl;
        while (ss >> ch)
        {
            // read line
            // cout << ch << endl;
            if (ch >= 'A' && ch <= 'Z')
            {
                int t;
                t = getIndex(ch);
                s.push(m[t]);
            }
            else if (')' == ch)
            {
                S a, b, c;
                b = s.top();
                s.pop();
                a = s.top();
                s.pop();
                if (a.y != b.x)
                {
                    err = true;
                    break;
                }
                c = x(a, b);
                sum += xx(a, b);
                s.push(c);
            }
        }
        if (err)
        {
            cout << "error" << endl;
        }
        else
        {
            cout << sum << endl;
        }
    }

    return 0;
}

标签:ch,20,Matrix,Chain,int,题解,矩阵,表达式,乘法
From: https://blog.51cto.com/HEX9CF/7703865

相关文章

  • Hadoop问题解决记(2)
     1.发现问题在对HBase集群进行压力测试过程中发现,当实际写入HBase和从HBase查询的量是平时的若干倍时(集群规模10~20台,每秒读写数据量在几十万条记录的量级),导致集群的读写出现一定程度的波动。具体如下:1)写端抛出以下异常信息:org.apache.hadoop.hbase.client.RetriesExha......
  • Hadoop问题解决记(1)
    最近在测试HBase时遇到一个非常奇怪的问题:集群有7台机器,其中1台Master,6台RegionServer。但是Master只能控制其中1台RegionServer,而无法控制其他5台RegionServer。打开master的日志文件,发现以下错误信息:2011-04-2216:37:21,242WARNorg.apache.hadoop.hbase.master.Assignment......
  • 文章《Semantic Kernel -- LangChain 的替代品?》的错误和疑问 探讨
    微信公众号文章SemanticKernel——LangChain的替代品?[1],它使用的示例代码是Python,他却发了这么一个疑问:支持的语言对比(因为SemanticKernel是用C#开发的,所以它对C#比较支持)如上所示。不清楚SemanticKernel为什么要用C#来开发,C#相比Python和JavaScript来说使用......
  • 『题解』P9688
    题目传送门思路:设有两个颜色\(x_1x_2\),两端分别为\(l_1\)\(r_1\),\(l_2\)\(r_2\)。通过观察可以发现,若满足\(x_1<x_2\)且\(r_1>l_2\)则\(x_1x_2\)一定是单调不下降的。那么我们可以先预处理出一个颜色可以与前面的哪些颜色构成单调不下降,然后用dp求出最终答案......
  • 题解 Coloring Brackets
    题目链接对于括号问题,考虑区间\(dp\)。这道题的括号序列是固定的,所以直接找出每个括号对应的括号在进行转化即可。设\(f_{l,r,0/1/2,0/1/2}\)表示\(l\simr\),左括号不染色/染红色/染蓝色,右括号不染色/染红色/染蓝色的方案数。若\(l,r\)是一对匹配括号,那么f_{l,r}便可以......
  • CF1661D Progressions Covering 题解
    最详细的题解题目传送门:ProgressionsCovering阅读前人题解时,限于个人能力有限,有一些地方想了好一会儿才懂。发现很多题解都是在@SDLTF_凌亭风等作者基础上延伸,但详细程度依旧有限,尽管这篇题解亦是站在他们基础上延伸的,这篇题解更为详细的点明了很多地方。本人第一次写题解,......
  • 洛谷 Power Tree 题解
    题目链接PowerTree分析将叶子节点按dfs序重标号后,每次控制操作可以转化为将子树内叶子节点所在区间加(或减)一个数不难可以想到将叶子区间进行差分每次对\(l\)到\(r\)的操作可以转化为将\(l\)上的数转移到\(r+1\)上每次操作后差分数组的和不变将所有点权变为\(0\)......
  • [题解] CF632F - Swimmers in the Pool
    CF632F-SwimmersinthePool题目传送门题意给定一个大小为\(n\timesn\)的矩阵\(A\)。假设\(A\)满足以下条件,那么称该矩阵为MAGIC,否则为NOTMAGIC,并输出对应的属性(即\(A\)是MAGIC还是NOTMAGIC)。$A_{i,j}=A_{j,i}$;$A_{i,i}=0$;$A_{i,j}\le......
  • GDCPC2023 B , D , F , K 题解
    和队友一起打的2023年广东省大学生程序设计竞赛重现赛,写了B,D,K,胡了一个F。D题目大意随着广东的建设与发展,越来越多人选择来到广东开始新生活。在一片新建的小区,有\(n\)个人要搬进\(m\)栋排成一行的房子,房子的编号从\(1\)到\(m\)(含两端)。房子\(u\)和\(v\)相邻......
  • LangChain大模型应用开发指南-传统编程范式思维的应用
    LangChain大模型应用开发指南-传统编程范式思维的应用上节课,我带领小伙伴们完成了baichuan2量化模型的OpenAI标准接口封装,并完成LangChain对大模型的调用与测试。没有看过的小伙伴可以点击链接查看:AI课程合集今天我们将正式开始LangChain大模型应用开发课程。组件总览上图......