3892: 4.6 快速计算——矩阵连乘

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:11 通过:7

题目描述

给定 n 个矩阵{A1,A2,A3,…,An},其中,Ai 和 Ai+1(i=1,2,…,n−1)是可乘的。


矩阵乘法如图 4-40 所示。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘 法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的计算量最小。 


例如: A1是 M5×10的矩阵; A2是 M10×100的矩阵; A3是 M100×2的矩阵。 那么有两种加括号的方法: (1)(A1 A2)A3; (2)A1(A2 A3)。 第 1 种加括号方法运算量:5×10×100+5×100×2=6000。 第 2 种加括号方法运算量:10×100×2+5×10×2=2100。 可以看出,不同的加括号办法,矩阵乘法的运算次数可能有巨大的差别! 



矩阵连乘问题就是对于给定 n 个连乘的矩阵,找出一种加括号的方法,使得矩阵连乘的 计算量(乘法次数)小。 








输入格式

输入一个T,表示有T组数据(1<=T<=10)

请输入矩阵的个数n (1<=n<=20)

请依次输入每个矩阵的行数和最后一个矩阵的列数


输入样例 复制

1
5
3 5 10 8 2 4

输出样例 复制

314

分类标签