5817: 4.6 快速计算
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：27
解决：21
题目描述
给定n个矩阵{A1，A2，A3，…，An}，其中，Ai和Ai+1( i=1，2，…，n-1)是可乘的。
用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量(乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。
用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量(乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。
例如：
A1是M5*10的矩阵
A2是M10*100的矩阵
A3是M100*2的矩阵
那么有两种加括号的方法：
（1）（A1A2）A3；
（2）A1（A2A3）
第1种加括号方法运算量:5×10×100+5×100×2=6000。第2种加括号方法运算量:10×100×2+5×10×2=2100。
可以看出，不同的加括号办法，矩阵乘法的运算次数可能有巨大的差别!
A1是M5*10的矩阵
A2是M10*100的矩阵
A3是M100*2的矩阵
那么有两种加括号的方法：
（1）（A1A2）A3；
（2）A1（A2A3）
第1种加括号方法运算量:5×10×100+5×100×2=6000。第2种加括号方法运算量:10×100×2+5×10×2=2100。
可以看出，不同的加括号办法，矩阵乘法的运算次数可能有巨大的差别!
输入
样例组数
t ( 0 < t < 10 )
矩阵个数
n ( 0 < n < 100 )
依次输入每个矩阵的行数和最后一个矩阵的列数
r1 r2 ... rn cn ( 0 < r < 100 )
t ( 0 < t < 10 )
矩阵个数
n ( 0 < n < 100 )
依次输入每个矩阵的行数和最后一个矩阵的列数
r1 r2 ... rn cn ( 0 < r < 100 )
输出
最小计算量的值
ans
ans
样例输入 复制
1
5
3 5 10 8 2 4样例输出 复制
314