1429-快速计算


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:3 难度:3


题目描述:

给定n个矩阵{A1A2A3…,An},其中,Ai Ai+1i=12,…,n1)是可乘的。矩阵乘法如图4-40所示。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的计算量最小。

例如:

A1M5×10的矩阵;

A2M10×100的矩阵;

A3M100×2的矩阵。

那么有两种加括号的方法:

1)(A1 A2A3

2A1A2 A3)。

1种加括号方法运算量:5×10×100+5×100×2=6000

2种加括号方法运算量:10×100×2+5×10×2=2100

不同的加括号办法,矩阵乘法的运算次数可能有巨大的差别!


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(0<n<100)表示矩阵的个数。
第2行共n+1个整数pi((0<pi<100)),是每个矩阵的行数和最后一个矩阵的列数。

输出描述:

对于每一组输入,输出矩阵连乘的最少乘法次数。
每组的输出占一行。

样例输入:

2
5
3 5 10 8 2 4
8
4 8 12 7 9 30 4 65 52

样例输出:

314
16516

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!