矩阵乘法计算量估算_

$\hspace{15pt}$ 对于给定的 $a$ 行 $b$ 列的矩阵： $A = \begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,b} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,b} \\ \vdots & \vdots & \ddots & \vdots \\ A_{a,1} & A_{a,2} & \cdots & A_{a,b} \end{bmatrix}$
$\hspace{15pt}$ 和 $b$ 行 $c$ 列的矩阵： $B = \begin{bmatrix} B_{1,1} & B_{1,2} & \cdots & B_{1,c} \\ B_{2,1} & B_{2,2} & \cdots & B_{2,c} \\ \vdots & \vdots & \ddots & \vdots \\ B_{b,1} & B_{b,2} & \cdots & B_{b,c} \end{bmatrix}$
$\hspace{15pt}$ 和 $c$ 行 $d$ 列的矩阵： $C = \begin{bmatrix} C_{1,1} & C_{1,2} & \cdots & C_{1,d} \\ C_{2,1} & C_{2,2} & \cdots & C_{2,d} \\ \vdots & \vdots & \ddots & \vdots \\ C_{c,1} & C_{c,2} & \cdots & C_{c,d} \end{bmatrix}$
$\hspace{15pt}$ 在计算 $A \times B \times C$ 时，不同的运算顺序会带来不同的运算量。例如， $(A \times B) \times C$ 的运算量是 $a \times b \times c + a \times c \times d$ ，而 $A \times (B \times C)$ 的运算量是 $b \times c \times d + a \times b \times d$ 。

$\hspace{15pt}$ 现在，对于给定的 $n$ 个矩阵的大小与运算式，请你计算出所需要的运算量。

$\hspace{15pt}$ 第一行输入一个整数 $n \left(1 \leqq n \leqq 15\right)$ 代表矩阵的个数。
$\hspace{15pt}$ 此后 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i \left(1 \leqq a_i, b_i \leqq 100\right)$ 代表第 $i$ 个矩阵的行数和列数。
$\hspace{15pt}$ 最后一行输入一个长度为 $1 \leqq {\rm len}(s) \leqq 10^3$ 的字符串 $s$ 代表运算式。运算式中只包含前 $n$ 个大写字母与括号，第 $i$ 个大写字母对应输入的第 $i$ 个矩阵，括号成对出现，保证运算式合法且正确。

矩阵乘法计算量估算

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题