程序设计能力实训

1172. 完全加括号的矩阵连乘积

单点时限: 2.0 sec

内存限制: 256 MB

$n$ 个矩阵的矩阵链 $A_1, A_2, \dots, A_n$,矩阵 $A_i$ 的规模为 $p_{i-1} \times p_i (1\leq i\leq n)$,$A_i$ 和 $A_{i+1}$是相容可乘的,求最优的完全加括号方案,使得依此次序计算矩阵链乘积:$\prod_{ i = 1 }^n A_i$所需要的乘法次数最少。

输入格式

第一行为正整数 $N$, 表示有 $N$ 组测试数据。

每组测试数据的第一行为 $n$,表示有 $n$ 个矩阵,$2\leq n\leq50$;

接下去的 $n$ 行,每行有两个整数 $x$ 和 $y$,表示矩阵的规模。

输出格式

对行每组数据,输出一行,每行一个整数,表示最小的乘法次数。

输出的结果在 $2^{64}$ 范围之内。

样例

Input
1
4
50 10
10 40
40 30
30 5
Output
10500

提示

一个大小为 $x \times y$ 和 $y \times z$ 的矩阵相乘所需的乘法次数为 $xyz$

不限期开放

题目列表