矩阵连乘积

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 t1.in 输出文件 t1.out

【问题描述】

由于矩阵乘法满足结合律，故其连乘积的计算可以有许多不同的计算次序。计算次序可以通过加括号的方式来确定。例如A1A2A3的连乘积可以有两种加括号的方式：((A1A2)A3)和(A1(A2A3))

矩阵连乘积的计算次序与连乘积的计算量有关。已知两个矩阵Apq和Aqr相乘的计算量为p*q*r，请确定矩阵连乘积A1A2...An的最小计算量的计算次序。

假设Ai的维数是Pi-1×Pi（ i=1,2,...,n ， 1<=n<10）

行　　组数M　　（1<=m<=6）

以下有M组，每组有两行，格式如下：　　

N

P0 P1 P2 ... Pn

输出文件(t1.out)：

共有M组，每组有两行，其格式为：

连乘积的最小计算量L （在[1,1000000]内）

矩阵连乘积的计算顺序

【输入输出样例】

样例输入：
2
2
2 3 5
3
2 5 100 2

样例输出：

30
(A1A2)
1020
(A1(A2A3))