U519157 矩阵连乘

本题改编自[P1753 矩阵链排序问题](https://www.luogu.com.cn/problem/P1753) 预备知识：矩阵乘法 矩阵乘法常常指的是一般矩阵乘法。设矩阵$A = (a_{ij})_{m \times n}$和$B = (b_{ij})_{m \times s}$,令$C=(c_{ij})_{m \times s}$。其中$c_{ij} = \displaystyle\sum_{k=1}^na_{ik}b_{kj}(1 \leq i \leq m,1\leq j\leq s)$，那么矩阵$C$称为矩阵$A$与$B$的乘积，记为$C=AB$ 或 $C=A \cdot B$。为方便，称被乘数$A$为左矩阵，乘数$B$为右矩阵。 >注意事项： >- 只有左矩阵的列数与右矩阵的行数相同的两个矩阵才能相乘。 >- 乘积矩阵第i行第j列处的元素等于左矩阵的第i行与右矩阵的第j列对应元素乘积之和，即$\big( AB\big)_{ij}=\displaystyle\sum_{k=1}^na_{ik}b_{kj}$。 >- 乘积矩阵的行数等于左矩阵的行数，列数等于右矩阵的列数。 >计算示例： >设$A = \begin{bmatrix}1 & -2 \\ 3 & 0 \\ -4 & 5\end{bmatrix}$,$B = \begin{bmatrix}-7 & 8 \\ 9 & 10\end{bmatrix}$,下面计算$AB$: $$ AB=\begin{bmatrix}1 & -2 \\ 3 & 0 \\ -4 & 5\end{bmatrix}\cdotp\begin{bmatrix}-7 & 8 \\ 9 & 10\end{bmatrix}\\ =\begin{bmatrix}1\times(-7)+(-2)\times9 & 1\times 8+(-2)\times10\\3\times(-7)+0\times9 & 3\times8+0\times10\\(-4)\times(-7)+5\times9 & (-4)\times8+5\times10\end{bmatrix} \\=\begin{bmatrix}-25 & -12 \\ -21 & 25 \\ 73 & 18\end{bmatrix} $$

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

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

输出的第一行包含一个整数，代表最小运算次数。 接下来的一行表示运算顺序，乘号省略

样例解释：样例1告诉我们有 $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 500$，$1 \leq p \leq 10^4$。