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

// HJ70 矩阵乘法计算量估算.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include<iostream>
#include<bits/stdc++.h>

using namespace std;
int a[15][2];//定义一个全局变量二维数组记录矩阵行列数信息
int main()
{
	int n;//输入有几个矩阵
	cin >> n;
	stack<pair<int,int>>dp;//定义一个栈用于存放每组矩阵的值
	for (int i = 0; i < n; i++)//输入每组矩阵的行列数存放在a数组中
	{
		cin >> a[i][0] >> a[i][1];
	}
	string s;//定义一个字符串表示需要计算的组合
	cin >> s;
	int res = 0;//定义一个用于输出结果的计数值
	for (int i = 0; i < s.size(); i++)//遍历运算组合字符串
	{
		if (s[i] == ')')//如果遇到右括号则需要计算
		{
			auto x = dp.top();//定义一个auto型变量x记录遇到右括号时dp栈的最后一组数据
			dp.pop();//删除dp栈的最后一组数据
			auto y = dp.top();//定义一个auto型变量y记录遇到右括号时dp栈的倒数第二组数据
			dp.pop();//删除dp栈的倒数第二组数据（上面删了最后一组了）
			if (x.first == y.second)//判断矩阵的行列对应关系
			{
				res += y.first * y.second * x.second;//计算可以做多少次乘法
				dp.push({ y.first, x.second });//将矩阵运算后新的组合存放到dp的最后一位
			}
			else if (y.first == x.second)//同上判断矩阵的行列对应关系
			{
				res += x.first * x.second * y.second;//计算可以做多少次乘法
				dp.push({ x.first,y.second }); //将矩阵运算后新的组合存放到dp的最后一位
			}
		}
		else if (s[i] != '(')//如果遇到左括号以外的字符则将目前的字符储存到dp栈里
		{
			int t = s[i]-'A';//由于都是大写字母故减去大写字母A的ASCII值得到下标
			dp.push({ a[t][0],a[t][1] });//将a数组对应下标的矩阵行列数信息存储到dp里记录
		}
	}
	cout << res << endl;//输出矩阵运算后的总乘积次数
	return 0;
}