矩阵乘法的运算量计算(华为OJ)

简介: 题目地址:https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b?tpId=37&&tqId=21293&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking题目内容矩阵乘法的运算量与矩阵乘法的顺序强相关。

题目地址:
https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b?tpId=37&&tqId=21293&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

题目内容

矩阵乘法的运算量与矩阵乘法的顺序强相关。

例如:
A是一个50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵

计算ABC有两种顺序:((AB)C)或者(A(BC)),前者需要计算15000次乘法,后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数

输入描述:
输入多行,先输入要计算乘法的矩阵个数n,每个矩阵的行数,列数,总共2n的数,最后输入要计算的法则
输出描述:
输出需要进行的乘法次数
示例1
输入

3
50 10
10 20
20 5
(A(BC))
输出

3500

思路

显然用栈做。但是细节要把控好。

考虑这样的数据,代码也应该能handle:

4
50 10
10 20
20 5
5 6
(A(BCD))
输出

9000

思路:
每个字母肯定不会重复,每个字母对应到一个(r,c)元组上,弄成结构体比较方便。

将字母括号串从左到右扫描,遇到')'则弹栈,一直弹到遇到'(',那么弹出的这些字母(对应到一个个矩阵,也对应到一个包含(r,c)维度信息的结构体),它们的列数c相乘,再乘以最后弹出元素(也即紧邻'('右边的字母)的行数r。
注意,这里还没有结束,遇到了'('应该把弹出这些元素计算结果进行保存,并且,更新一下维护的字母括号序列的元素,我的做法是把原有的“(XXXXZ)”这个东西用Z来替代,因为Z的列数c后续还是会被使用。

放码过来


#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <stack>

using namespace std;


void EX21_clean() {
    int n;

    struct Dim { int r, c; };

    while (cin >> n) {
        vector<Dim> vd;
        Dim dim;

        for (int i = 0; i < n; i++) {
            cin >> dim.r >> dim.c;
            vd.push_back(dim);
        }

        string s; cin >> s;
        stack<Dim> stk;
        int ans = 0;
        stack<char> cal;
        int delta;

        int idx;
        char ch1, ch2;

        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')') {
                if (cal.size() != 1) {
                    ch1 = cal.top(); cal.pop();
                    if (ch1 == '(') {
                        continue;
                    }
                    idx = ch1 - 'A';
                    dim = vd[idx];

                    delta = dim.c;
                    while (!cal.empty()) {
                        ch2 = cal.top(); cal.pop();
                        idx = ch2 - 'A';
                        if (ch2 == '(') {
                            cal.push(ch1); //注意此处
                            break;
                        }
                        dim = vd[idx];
                        delta *= dim.c;
                    }
                    delta *= dim.r;
                    ans += delta;
                }
            }
            else {
                cal.push(s[i]);
            }
        }
        cout << ans << endl;
    }
}

int main() {
    //EX1();
    //EX2();
    //EX3();
    //EX4();
    //EX5();
    //EX6();
    //EX7();
    
    //EX11();
    //EX12();
    //EX13();
    //EX14();
    //EX15();
    //EX16();
    //EX17();

    EX21_clean();

    return 0;
}
目录
相关文章
|
小程序 安全 物联网
【经验分享】支付宝小程序常用appId
【经验分享】支付宝小程序常用appId
3397 6
|
JavaScript
使用nodejs连接ftp上传下载
使用nodejs连接ftp,进行ftp的操作,包括列表、上传、下载以及速率等。
使用nodejs连接ftp上传下载
|
机器学习/深度学习 算法 TensorFlow
维特比算法(Viterbi algorithm)
维特比算法(Viterbi algorithm)是一种用于解码隐马尔可夫模型(Hidden Markov Model,HMM)的动态规划算法。它用于找到给定观测序列条件下的最有可能的隐藏状态序列。
825 1
|
7月前
|
域名解析 人工智能 缓存
无前端经验如何快速搭建游戏站:使用 windsurf 从零到上线的详细指南
本指南涵盖游戏站页面初稿设计、工具配置、内容设计与功能实现及部署上线的全流程。通过参考优秀网站设计,利用v0.dev平台完成页面布局和样式调整,并下载代码进行后续开发。使用Windsurf配置工作空间规则,确保以用户易懂的方式推进项目。逐步实现多语言支持、favicon设置、嵌入游戏等功能,确保网页专业且用户体验良好。最后通过购买域名、GitHub托管代码、Vercel部署等步骤将游戏站成功上线。
327 10
|
存储 Java 索引
Java 中 ArrayList 和 LinkedList 之间的区别
【8月更文挑战第22天】
281 1
|
存储 Go 索引
GOLANG MAP 底层实现
GOLANG MAP 底层实现
259 2
|
供应链 自动驾驶 物联网
5G通信
7月更文挑战第2天
|
11月前
|
Cloud Native 持续交付 数据安全/隐私保护
云原生时代的微服务架构设计原则
在数字化浪潮中,企业纷纷上云以获得更大的灵活性和扩展性。云原生技术因此成为现代软件开发的核心。本文将深入探讨在云原生环境下如何设计高效、可靠的微服务架构,涵盖关键设计原则、最佳实践以及面临的挑战。我们将通过实际案例分析,揭示如何在云原生生态中构建和维护微服务,确保系统的稳定性和可维护性。
|
域名解析 监控 负载均衡
智能DNS解析:自动选择最快服务器的奥秘
【9月更文挑战第7天】智能DNS解析是一种根据用户网络环境和服务器负载动态选择最佳服务器的技术,显著提升了访问速度与稳定性。本文详细介绍了其工作原理,包括实时监控、数据分析和路由选择,并探讨了自动选择最快服务器背后的算法策略,如负载均衡、地理位置识别及实时测试。附带示例代码帮助理解其基本实现过程。
728 0
|
Java 索引
深入浅出JVM(五)之Java中方法调用
深入浅出JVM(五)之Java中方法调用