给定n个矩阵链<A1,A2,...,An>，矩阵Ai的规模为pi-1*pi（1≤i≤n），求完全括号化方案，使得A1A2,...An所需标量乘法次数最小。
代码语言：javascript复制#include<iostream>
#include<map>
#include<string>
#include<stack>
using namespace std;
struct matrix {
int row;
int column;
};
int main() {
int n; string ch;
string str;
int li, co;
map<string, matrix>m;
cin >> n;
for (int i = 0; i < n; i ) {
cin >> ch >> li >> co;
m[ch].row = li;
m[ch].column = co;
}
while ((cin >> str)){
stack<string>s;
string a, b;
int sum = 0;
bool flag = true;
for (int i = 0; i < str.length(); i ) {
if (str[i] == '(') continue;
else if (str[i] == ')') {
a = s.top(); s.pop();
b = s.top(); s.pop();
if (m[b].column == m[a].row) {
sum = m[b].row*m[b].column*m[a].column;
string ba;
ba = b a;
s.push(ba);
m[ba].row = m[b].row;
m[ba].column = m[a].column;
}
else {
flag = false;
break;
}
}
else {
string s2;
s2 = str[i];
s.push(s2);
}
}
if(flag) cout << sum << endl;
else cout << "error" << endl;
}
return 0;
}
