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

#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;
//毕竟也不知道多少个矩阵，还是用堆栈。矩阵类封装，思路挺好的
struct matrix{
    int x,y;
};
void cal(string s,matrix arr[],int n){
    stack<matrix> m;
    int sum=0,i=0;
    for(auto c:s){
        if(c==')'){
            matrix m0=m.top();
            m.pop();
            sum+=m0.x*m0.y*m.top().x;    //2矩阵乘法数计算
            m.top().y=m0.y;    //栈顶矩阵大小更新为乘后结果
        }else if(c!='('){    //矩阵压栈
            m.push(arr[i++]);
        }
    }
    cout<<sum;
}
int main(){
    int n;
    string s;
    cin>>n;
    matrix *arr=new matrix[n];
    for(int i=0;i<n;i++){
        cin>>arr[i].x>>arr[i].y;
    }
    cin>>s;
    cal(s,arr,n);
    return 0;
}