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

#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct Matrix {
    unsigned n;
    unsigned m;
};


int main() {
    unsigned a;
    cin >> a;
    Matrix *matrix = new Matrix[a];
    for (unsigned i = 0; i != a; ++i) {
        cin >> matrix[i].m >> matrix[i].n;
    }
    string cmd;
    cin >> cmd;

    int sum = 0;
    stack<Matrix> st_m;
    stack<char> st_c;
    unsigned flag = 0;
    for (char c : cmd) {
        if (c == '(') {
            st_c.push(c);
            continue;
        } else if (c == ')') {
            Matrix m2 = st_m.top();
            st_m.pop();
            Matrix &m1 = st_m.top();
            sum += m1.m * m1.n * m2.n;
            m1.n = m2.n;
            continue;
        }
        st_m.push(matrix[flag]);
        flag++;
    }

    delete[] matrix;
    cout << sum << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")