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

#include <cctype>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

// 内积里面自己加上
// 然后返回i*j*k的j*k
string matrix_chain_order(std::vector<int>& p, string& s, int& sum) {
    std::queue<string> matrixs;
    for (int i = 0; i < s.size(); ++i) {
        // 解决连乘
        if (std::isalpha(s[i])) {
            int j = i + 1;
            while (std::isalpha(s[j])) {
                ++j;
            }
            if (i == j - 1) {
                string s12;
                s12 += s[i];
                matrixs.push(s12);
            } else {
                string s12;
                s12 += s[i];
                int row = p[s[i] - 'A'];
                for (int k = i + 1; k < j; ++k) {
                    sum += row * p[s[k] - 'A'] * p[s[k] - 'A' + 1];
                }
                s12 += s[j - 1];
                matrixs.push(s12);
            }
            i = j - 1;
        } else {
            int j = i + 1;
            int quote = 1;
            while (j < s.size()) {
                if (s[j] == '(') {
                    ++quote;
                } else if (s[j] == ')') {
                    --quote;
                }
                if (!quote) {
                    break;
                }
                ++j;
            }
            string sub = s.substr(i + 1, j - i - 1);
            matrixs.push(matrix_chain_order(p, sub, sum));
            i = j;
        }
    }
    string source = matrixs.front();
    string first = matrixs.front();
    matrixs.pop();
    string second;
    while (!matrixs.empty()) {
        second = matrixs.front();
        matrixs.pop();
        if (first.size() == 2) {
            sum += p[first[0] - 'A'] * p[first[1] - 'A' + 1] * p[second.back() - 'A' + 1];
        } else {
            sum += p[first[0] - 'A'] * p[first[0] - 'A' + 1] * p[second.back() - 'A' + 1];
        }
        first = second;
    }
    string sss;
    sss += source.front();
    if (!second.empty() && sss.back() != second.back()) {
        sss += second.back();
    } else if (source.back() != sss.back()) {
        sss += source.back();
    }
    return sss;
}

int main() {
    int a;
    while (cin >> a) {
        std::vector<int> p(a + 1);
        if (!a) {
            cout << a << endl;
            continue;
        }
        int row;

        for (int i = 0; i < a; ++i) {
            cin >> p[i] >> row;
        }
        p[a] = row;
        string s;
        cin >> s;
        int sum = 0;
        matrix_chain_order(p, s, sum);
        cout << sum << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

一个括号解析加字符串运算这么多变种，记录做起来吃力的题