3020 - 矩阵连乘

矩阵是按行和列排列的数字集合。矩阵A（r行s列）和矩阵B（p行q列）能够相乘的条件为s=p，即前一个矩阵的列数要等于后一个矩阵的行数。完成乘法AB共需要r*s*q次乘法。 矩阵乘法满足结合律，但不满足交换律，即一般情况下AB和BA并不相等，但(AB)C和A(BC)的结果是一样的。 现有n个矩阵连乘，记为A_1A_2…A_n，A_1的行列分别为p_0和p_1，A_2的行列为p_1和p_2，以此类推。请设计算法，给出矩阵连乘的顺序，使总计算量最小。总计算量为每次矩阵相乘的乘法次数之和。

第一行为一个数n。 第二行为n+1个数，分别为p0,p1,…,pn。

矩阵连乘所需要的最少乘法次数。

数据规模和约定

对30%的数据，1\le n\le 100, 1\le pi \le 10000。

对100%的数据，1\le n\le 1000, 1\le pi\le 10000。

动规专题