题目描述
给定 n 个矩阵,已知第 i 个矩阵 Mi 的大小为 wi 行 wi+1 列,而我们并不关心其内容。我们考虑将其按照顺序相乘(称其为链乘积):
M=M1×M2×⋯×Mn
矩阵乘法并不满足交换律,但是其满足结合律,因此我们可以通过合理安排结合顺序,尽可能减少需要的运算次数。在此题中,我们定义将一个大小为 a×b 的矩阵乘以一个大小为 b×c 的矩阵需要 abc 次运算。
请你算出将题目所给的 n 个矩阵进行链乘积所需的最少运算数。为了方便起见,你不需要构造方案。
输入格式
输入的第一行为一个正整数 n,代表矩阵的数量。
接下来的一行包含 n+1 个正整数,其中第 i 个整数为 wi,含义参考题目描述。
输出格式
输出包含一个整数,代表最小运算次数。
3
5 3 2 6
90
提示
样例解释:样例告诉我们有 n=3 个矩阵,其大小分别是 5×3,3×2 和 2×6。分别考虑两种乘法顺序:
- 先将 M1 和 M2 相乘得到一个 5×2 的矩阵,然后和 M3 相乘,此时运算次数为 5×3×2+5×2×6=90;
- 先将 M2 和 M3 相乘得到一个 3×6 的矩阵,然后和 M1 相乘,此时运算次数为 3×2×6+5×3×6=126。
本题要求运算次数最少,因此答案为 90。
对所有的数据,1≤n≤2×106,1≤w≤104。其中:
- 对 30% 的数据,满足 n≤500;
- 对另外 30% 的数据,满足 n≤2×105。