矩阵连乘问题

题目描述

给定n个矩阵{ $A_1$, $A_2$, …, $A_n$ }，其中$A_i$与$A_{i+1}$是可乘的，i = 1, 2, …, n-1，确定矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的乘法次数最少。

输入描述

输入文件包含多个测试数据，每个测试数据占一行，首先是正整数n，n<100，表示矩阵的个数；然后是n+1个正整数（设序号为0~n），第i-1、i个整数描述了第i个矩阵$A_i$的维度。

输出描述

对每个测试数据表示的矩阵乘法，输出最少的乘法次数。

样例输入

6 30 35 15 5 10 20 25
3 10 100 5 50

样例输出

15125
7500