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

单点时限: 2.0 sec

内存限制: 256 MB

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

输入格式

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

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

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

输出格式

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

输出的结果在 范围之内。

样例

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

提示

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

190 人解决,352 人已尝试。

281 份提交通过,共有 983 份提交。

6.4 EMB 奖励。

创建: 12 年,10 月前.

修改: 1 年,2 月前.

最后提交: 10 小时前.

来源: N/A

题目标签
DP