UVA442 矩阵链乘 Matrix Chain Multiplication
题目描述
假设你必须评估一种表达形如 $A\times B\times C\times D\times E$，其中 $A,B,C,D,E$ 是矩阵。既然矩阵乘法是关联的，那么乘法的顺序是任意的。然而，链乘的元素数量必须由你选择的赋值顺序决定。
例如，$A,B,C$ 分别是 $50 \times 10$，$10 \times 20$ 和 $20 \times 5$ 的矩阵。现在有两种方案计算 $A \times B \times C$，即 $（A \times B) \times C$ 和 $A\times(B \times C)$。第一个要进行 $15000$ 次基本乘法，而第二个只进行 $3500$ 次。
你的任务就是写出一个程序判定以给定的方式相乘需要多少次基本乘法计算。
输入格式
输入包含两个部分：矩阵和表达式。
输入文件的第一行包含了一个整数 $n(1 \leq n \leq 26)$，代表矩阵的个数。接下来的n行每一行都包含了一个大写字母，说明矩阵的名称，以及两个整数，说明行与列的个数。
第二个部分严格遵守以下的语法：
```text
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
```
输出格式
对于每一个表达式，如果乘法无法进行就输出 `error`。否则就输出一行包含计算所需的乘法次数。
感谢 @onceagain 提供翻译