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

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

using namespace std;

int a[15][2];

int main()
{
	int n; string s;
	while (cin >> n)
	{
		stack<pair<int, int>>dp;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				cin >> a[i][j];
			}
		}
		cin >> s;
		int res = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == ')')
			{
				auto y = dp.top();
				dp.pop();
				auto x = dp.top();
				dp.pop();
				if (x.second == y.first)
				{
					res += x.first * x.second * y.second;
					dp.push({ x.first, y.second });
				}
				else if (x.first == y.second)
				{
					res += y.first * y.second * x.second;
					dp.push({ y.first,x.second });
				}
			}
			else if (s[i] != '(')
			{
				dp.push({ a[s[i] - 'A'][0],a[s[i] - 'A'][1] });
			}
		}
		cout << res << endl;
	}
	return 0;
}