3102: 【UVA 442】Matrix Chain Multiplication

假设您必须计算一个表达式，如ABCDE，其中A、B、C、D和E是矩阵。由于矩阵乘法是关联的，所以执行乘法的顺序是任意的。然而，所需的初等乘法的数量很大程度上取决于求值顺序您可以选择。 例如，设A为50*10矩阵，B为10*20矩阵，C为20*5矩阵。有两个计算ABC的不同策略，即（AB）C和A（B*C）。第一个需要15000次基本乘法，但第二个只需要3500次。你的工作是编写一个程序，确定所需的初等乘法的数量

输入包含矩阵和表达式两部分。在第1部分，第1行包含一个整数n （1≤n ≤26），代表矩阵的个数；接下来的n 行，每行都包含了一个大写字母来表示矩阵的名称，以及两个整数来表示矩阵的行数和列数。第2部分是一个矩阵或矩阵表达式。

对于每一个表达式，如果乘法无法进行，则输出“Error”，否则输出所需的乘法运算次数。

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

0
0
0
error
10000
error
3500
15000
40500
47500
15125