1559. 最优矩阵连乘

【题目描述】

一个$n\times m$矩阵由$n$行$m$列共$n\times m$个数排列而成。

两个矩阵$A$和$B$可以相乘当且仅当$A$的列数等于$B$的行数。

一个$n\times m$的矩阵乘以一个$m\times p$的矩阵等于一个$n\times p$的矩阵，其所需要的乘法运算量为$n\times m\times p$。
矩阵乘法满足结合律，$A\times B \times C$可以表示成$(A\times B)\times C$或者是$A\times (B\times C)$，两者的运算量却不同。例如当$A$是一个$2\times 3$的矩阵，$B$是一个$3\times 4$的矩阵，$C$是一个$4\times 5$的矩阵时，$(A\times B)\times C$所需要的运算量为$64$，而$A\times (B\times C)$的运算量为$90$，显然第一种顺序节省运算量。

现在给出$N$个矩阵，请你设计一个乘法顺序使得需要的乘法运算量最小。

【输入格式】

第一行一个整数$N(N\leq 100)$，表示矩阵的个数。
第二行$N+1$个整数$A_i$，用来表示$N$个矩阵的行数和列数，具体的第$i$个矩阵是一个$A_i$行$A_{i+1}$列的矩阵。

【输出格式】

最优的运算量，所有的数据均保证结果不超过$2^{31}-1$。

【样例输入】

3
2 3 4 5

【样例输出】

64

【样例解释】

三个矩阵$A,B,C$的大小分别为$2\times 3$、$3\times 4$、$4\times 5$。

最优的计算顺序为$(A\times B)\times C$，计算$A\times B$需要的运算量为$2\times 3\times 4=24$，得到的矩阵$D$的大小为$2\times 4$，计算$D\times C$需要的运算量为$2\times 4\times 5=40$，故而需要的总运算量为$64$。