题解 | #矩阵乘法计算量估算#

解题思路

1. 题目要求：

   • 计算矩阵乘法的运算次数
   • 根据给定的计算顺序(括号表达式)来确定运算顺序
   • 矩阵个数n:
   • 矩阵行列数:

2. 关键点：

   • 使用栈来存储待计算的矩阵信息
   • 遇到右括号时，处理最近的两个矩阵相乘
   • 计算量 = 第一个矩阵的行数 × 第一个矩阵的列数 × 第二个矩阵的列数

代码

while True:
    try:
        n = int(input())
        arr = []
        order = []
        res = 0
        # 读取矩阵维度信息
        for i in range(n):
            arr.append(list(map(int, input().split())))
        
        # 读取计算顺序
        f = input()
        for i in f:
            if i.isalpha():
                # 将字母转换为对应矩阵的维度信息
                order.append(arr[ord(i)-65])
            elif i == ')' and len(order) >= 2:
                # 遇到右括号，处理最近的两个矩阵
                b = order.pop()
                a = order.pop()
                # 计算乘法运算次数并累加
                res += a[0] * a[1] * b[1]
                # 将结果矩阵压入栈中
                order.append([a[0], b[1]])
        print(res)
    except:
        break

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[][] arr = new int[n][2];
            List<int[]> order = new ArrayList<>();
            int res = 0;
            
            // 读取矩阵维度信息
            for (int i = 0; i < n; i++) {
                arr[i][0] = sc.nextInt();
                arr[i][1] = sc.nextInt();
            }
            
            // 读取计算顺序
            String f = sc.next();
            for (char c : f.toCharArray()) {
                if (Character.isLetter(c)) {
                    // 将字母转换为对应矩阵的维度信息
                    order.add(arr[c - 'A']);
                } else if (c == ')' && order.size() >= 2) {
                    // 遇到右括号，处理最近的两个矩阵
                    int[] b = order.remove(order.size() - 1);
                    int[] a = order.remove(order.size() - 1);
                    // 计算乘法运算次数并累加
                    res += a[0] * a[1] * b[1];
                    // 将结果矩阵压入栈中
                    order.add(new int[]{a[0], b[1]});
                }
            }
            System.out.println(res);
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<vector<int>> arr(n, vector<int>(2));
        vector<vector<int>> order;
        int res = 0;
        
        // 读取矩阵维度信息
        for (int i = 0; i < n; i++) {
            cin >> arr[i][0] >> arr[i][1];
        }
        
        // 读取计算顺序
        string f;
        cin >> f;
        for (char c : f) {
            if (isalpha(c)) {
                // 将字母转换为对应矩阵的维度信息
                order.push_back(arr[c - 'A']);
            } else if (c == ')' && order.size() >= 2) {
                // 遇到右括号，处理最近的两个矩阵
                vector<int> b = order.back();
                order.pop_back();
                vector<int> a = order.back();
                order.pop_back();
                // 计算乘法运算次数并累加
                res += a[0] * a[1] * b[1];
                // 将结果矩阵压入栈中
                order.push_back({a[0], b[1]});
            }
        }
        cout << res << endl;
    }
    return 0;
}

算法分析

1. 时间复杂度：

   • n为表达式长度
   • 每个字符只需处理一次

2. 空间复杂度：

   • 需要一个栈来存储矩阵信息