题目描述
给定 $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
输入 #1
1 | |
输出 #1
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 2 \times 10^6$，$1 \leq w \leq 10^4$。其中：
- 对 $30%$ 的数据，满足 $n \leq 500$；
- 对另外 $30%$ 的数据，满足 $n \leq 2 \times 10^5$。
题解
状态定义和转移
定义 $f(l,r)$ 表示从 $M_l$ 到 $M_r$ 所有矩阵相乘的最小代价。显然， $$ f(l,r) = \min_{l \le k < r}\set{f(l,k) + f(k+1,r) + w_l \times w_{k+1} \times w_{r+1}} $$ 该算法复杂度为 $\Theta(n^3)$。
DP 优化
查了各种资料发现本题 $O(n \log n)$ 正解是 Hu-Sing 算法，贴个论文解读：[论文解析] Hu-Shing 算法 - 快速求出矩阵链乘积最优解 - 洛谷专栏。
