HJ70 矩阵乘法计算量估算

输入：

3
50 10
10 20
20 5
(A(BC))

输出：

3500

考察基础，对string的用法是否熟悉，没有太大技巧，难在对输入的处理。

注解在代码中说明；

代码： 

#include
#include
#include
#include
using namespace std;
int n;//个数
//注解：
//substr() 返回截取的字符串，原字符串不改变

//replace(pos.n,"")替换字符串；如果用该方式替换字符，则下次查找不到
//例：string s="pppll";
//s.replace(3,2,"*")----输出s：ppp*;
//s.find('*')---查找不到！
//replace('a','*');-替换指定字符

//s.erase(pos,n)删除pos位置开始的n个字符;
//s.insert(pos,1,'*')在 pos 位置插入 ‘*’字符


//字符递增表示 char c=‘a’;c++;输出 c:----b;

//m存储临接表式数据结构

unordered_map>m;
int countnum = 0;
bool flag = true;
char var_change ='a';
void deal_fun(string& s)
{
    if (s.size() <= 1) {
        flag = false; return;
    }
    int pos = s.find(')');
    if (pos != -1)
    {
        string s2 = s.substr(pos - 2, 2);
        countnum += m[s2[0]][0] * m[s2[0]][1] * m[s2[1]][1];
        vectortmp2;
        tmp2.push_back(m[s2[0]][0]);
        tmp2.push_back(m[s2[1]][1]);
        m[var_change] = tmp2;
        s.erase(pos - 3, 4);
        s.insert(pos - 3, 1,var_change);
        var_change++;
        deal_fun(s);
        if (!flag)return;
    }
    for (int i = 0; i < s.size(); i++)
    {
        string s2 = s.substr(0, 2);
        countnum += m[s2[0]][0] * m[s2[0]][1] + m[s2[1]][1];
        vectortmp2;
        tmp2.push_back(m[s2[0]][0]);
        tmp2.push_back(m[s2[1]][1]);
        m['#'] = tmp2;
        s.erase(0, 2);
        s.insert(0, 1, '#');
        deal_fun(s);
        if (!flag)return;
    }
}
int main()
{
    cin >> n;
    vector>v;
    for (int i = 0; i < n; i++)
    {
        vectortmp(2, 0);
        cin >> tmp[0] >> tmp[1];
        v.push_back(tmp);
    }
    string s;
    cin >> s;
    int a = 0;
    for (char it : s)
    {
        if (it <= 'Z' && it >= 'A')
        {
            m[it] = v[a]; a++;
        }
    }
    deal_fun(s);
    cout << countnum;
    return 0;
}