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

个人感觉此题难度中规中矩，侧重基础，难在对输入的处理，没有什么技巧性的方法；

对重复子问题，可以采用递归解法；

代码：

#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int n;//个数
unordered_map<char, vector<int>>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];
        vector<int>tmp2;
        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];
        vector<int>tmp2;
        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<vector<int>>v;
    for (int i = 0; i < n; i++)
    {
        vector<int>tmp(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;
}

注解： //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存储临接表式数据结构