算法分析与设计习题 (参考)

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

单点时限: 2.0 sec

内存限制: 256 MB

个矩阵的矩阵链 ,矩阵 的规模为 是相容可乘的,求最优的完全加括号方案,使得依此次序计算矩阵链乘积:所需要的乘法次数最少。

输入格式

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

每组测试数据的第一行为 ,表示有 个矩阵,;

接下去的 行,每行有两个整数 ,表示矩阵的规模。

输出格式

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

输出的结果在 范围之内。

样例

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

提示

一个大小为 的矩阵相乘所需的乘法次数为