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

#include<iostream>
#include<vector>
#include<map>
#include<sstream>
using namespace std;
//采用深度优先遍历的递归方法
//每一层中 将最外层括号都看做是一个整体，然后从左往右依次将所有矩阵向量放入数组中，再依次相乘

map<char, pair<int, int>> table;//存储字母对应的矩阵向量
int times = 0;//总计算次数

pair<int, int> getNewMatrix(pair<int, int> A,
                            pair<int, int> B) {//两矩阵相乘的结果 每调用一次times就会增加
    int row = A.first;
    int col = B.second;
    times += row * col * A.second;
    return { row, col };
}

pair<int, int> dfs(string s, int left, int right) {//递归调用

    vector<pair<int, int>> matrixs;//当前层所有的矩阵
    for (int i = left; i <= right; i++) {
        int layer = 0;//标记括号层次

        if (isalpha(s[i])) {//若当前位是字母，就直接将其放入尾端
            matrixs.push_back(table[s[i]]);
        }
        if (s[i] == '(') {//找出最外层括号的位置
            int j = i;
            for (; j <= right; j++) {
                if (s[j] == '(')layer++;
                else if (s[j] == ')')layer--;
                if (layer == 0)break;
            }
            matrixs.push_back(dfs(s, i + 1, j - 1));//递归计算当前括号内的矩阵
            i = j;
        }
    }

    pair<int, int> matrix = matrixs[0];
    for (int i = 1; i < matrixs.size(); i++) {
        matrix = getNewMatrix(matrix, matrixs[i]);
    }

    return matrix;
}



int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> inputMats;
    for (int i = 0; i < n; i++) {
        int key;
        int value;
        cin >> key >> value;
        inputMats.push_back({ key, value });
    }
    string s;
    cin >> s;

    istringstream iss(s);
    char ch;
    int index = 0;
    while (iss >> ch) {
        if (isalpha(ch)) {
            table[ch] = inputMats[index++];
        }
    }
  	//以上均为输入内容
    dfs(s, 0, s.size() - 1);

    cout << times << endl;

}