Description给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,…,n-1。
如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
Input输入包含多组测试数据。
第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n,表示有n个矩阵连乘,接下来一行有n+1个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开.Output你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的矩阵最少连乘积次数.SampleInput1310100550SampleOutput7500
1