矩阵链排序问题

题目描述

给定 $n$ 个矩阵,已知第 $i$ 个矩阵 $M_i$ 的大小为 $w_i$ 行 $w_{i+1}$ 列,而我们并不关心其内容。我们考虑将其按照顺序相乘(称其为链乘积): $$ M = M_1 \times M_2 \times \cdots \times M_n $$ 矩阵乘法并不满足交换律,但是其满足结合律,因此我们可以通过合理安排结合顺序,尽可能减少需要的运算次数。在此题中,我们定义将一个大小为 $a \times b$ 的矩阵乘以一个大小为 $b \times c$ 的矩阵需要 $abc$ 次运算。 请你算出将题目所给的 $n$ 个矩阵进行链乘积所需的最少运算数。为了方便起见,你不需要构造方案。

输入输出格式

输入格式


输入的第一行为一个正整数 $n$,代表矩阵的数量。 接下来的一行包含 $n+1$ 个正整数,其中第 $i$ 个整数为 $w_i$,含义参考题目描述。

输出格式


输出包含一个整数,代表最小运算次数。

输入输出样例

输入样例 #1

3
5 3 2 6

输出样例 #1

90

说明

样例解释:样例告诉我们有 $n = 3$ 个矩阵,其大小分别是 $5 \times 3$,$3 \times 2$ 和 $2 \times 6$。分别考虑两种乘法顺序: - 先将 $M_1$ 和 $M_2$ 相乘得到一个 $5 \times 2$ 的矩阵,然后和 $M_3$ 相乘,此时运算次数为 $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$; - 先将 $M_2$ 和 $M_3$ 相乘得到一个 $3 \times 6$ 的矩阵,然后和 $M_1$ 相乘,此时运算次数为 $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$。 本题要求运算次数最少,因此答案为 $90$。 --- 对所有的数据,$1 \leq n \leq 2 \times 10^6$,$1 \leq w \leq 10^4$。其中: - 对 $30\%$ 的数据,满足 $n \leq 500$; - 对另外 $30\%$ 的数据,满足 $n \leq 2 \times 10^5$。