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

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

int main() {
    int n,sum=0;
    char c;
    stack<char> cal;                        //存放表达式
    cin>>n;
    vector<pair<int,int>> matrix;           //存放输入矩阵以及计算中产生的矩阵
    for(int i=0;i<n;i++){                   //输入矩阵
        int x,y;
        cin>>x>>y;
        matrix.push_back(make_pair(x,y));
    }
    while(cin>>c){
        if(c=='('||(c<='Z'&&c>='A')){       //'('与字母入栈
            cal.push(c);
        }
        if(c==')'){                         //输入')'开始计算，因为两个括号间只有两个矩阵相乘的一次计算，故不使用循环
            int i=cal.top()-'A';            //记录第二个矩阵的下标
            cal.pop();                      //弹出矩阵
            int j=cal.top()-'A';            //记录第一个矩阵的下标
            cal.pop();                      //弹出矩阵
            sum+=matrix[j].first*matrix[j].second*matrix[i].second;//计算量
            cal.pop();                      //弹出'('
            cal.push(matrix.size()+'A');    //记录新产生的矩阵，下标为matrix.size()+'A'
            matrix.push_back(make_pair(matrix[j].first,matrix[i].second));
        }
    }
    cout<<sum<<endl;
}
// 64 位输出请用 printf("%lld")