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

#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;
// 需要特别留意左括号'(' 处理不当会计算错误
struct Mat {
    int row;
    int col;
    void Cross(const Mat& l, const Mat& r) {
        row = l.row;
        col = r.col;
    }
    int GetVal(const Mat& r) {
        return row * col * r.col;
    }
};

int Cal(vector<Mat*>& pool, stack<Mat*>& s, list<Mat*>& cur) {
    if(cur.size() > 1) {
        auto p2 = cur.back();
        cur.pop_back();
        auto p1 = cur.back();
        cur.pop_back();
        auto r = new Mat();
        pool.push_back(r);
        //printf("%dX%dX%d\n", p1->row, p1->col, p2->col);
        r->Cross(*p1, *p2);
        cur.push_back(r);
        return p1->GetVal(*p2);
    } else {
        return 0;
    }
}

int main() {
    int n;
    cin >> n;
    vector<Mat> all(n);
    int total = 0;
    for(auto& v : all) {
        cin >> v.row >> v.col;
    }
    vector<Mat*> result;
    string cmd;
    cin >> cmd;
    stack<Mat*> s;
    list<Mat*> cur;
    for(auto c : cmd) {
        if(c == '(') {
            if(cur.size()) {
                s.push(cur.front());
                cur.pop_front();
            } else {
			  	// 必须加入一个空指针作为标识
                s.push(nullptr);
            }
        } else if(c == ')') {
            if(s.size()) {
                auto m = s.top();
                s.pop();
                if(m) {
                    cur.push_front(m);
                    total += Cal(result, s, cur);
                }
            }
        } else {
            auto id = c - 'A';
            cur.push_back(&all[id]);
            total += Cal(result, s, cur);
        }
    }
    cout << total << endl;
    for(auto v : result) {
        delete v;
    }
}
// 64 位输出请用 printf("%lld")