luogu#P1753. 矩阵链排序问题

    ID: 5811 远端评测题 1500ms 512MiB 尝试: 420 已通过: 1 难度: 7 上传者: 标签>动态规划,dp图论区间 dp图论建模左偏树Ad-hoc

矩阵链排序问题

题目描述

给定 nn 个矩阵,已知第 ii 个矩阵 MiM_i 的大小为 wiw_iwi+1w_{i+1} 列,而我们并不关心其内容。我们考虑将其按照顺序相乘(称其为链乘积):

M=M1×M2××MnM = M_1 \times M_2 \times \cdots \times M_n

矩阵乘法并不满足交换律,但是其满足结合律,因此我们可以通过合理安排结合顺序,尽可能减少需要的运算次数。在此题中,我们定义将一个大小为 a×ba \times b 的矩阵乘以一个大小为 b×cb \times c 的矩阵需要 abcabc 次运算。

请你算出将题目所给的 nn 个矩阵进行链乘积所需的最少运算数。为了方便起见,你不需要构造方案。

输入格式

输入的第一行为一个正整数 nn,代表矩阵的数量。

接下来的一行包含 n+1n+1 个正整数,其中第 ii 个整数为 wiw_i,含义参考题目描述。

输出格式

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

3
5 3 2 6
90

提示

样例解释:样例告诉我们有 n=3n = 3 个矩阵,其大小分别是 5×35 \times 33×23 \times 22×62 \times 6。分别考虑两种乘法顺序:

  • 先将 M1M_1M2M_2 相乘得到一个 5×25 \times 2 的矩阵,然后和 M3M_3 相乘,此时运算次数为 5×3×2+5×2×6=905 \times 3 \times 2 + 5 \times 2 \times 6 = 90
  • 先将 M2M_2M3M_3 相乘得到一个 3×63 \times 6 的矩阵,然后和 M1M_1 相乘,此时运算次数为 3×2×6+5×3×6=1263 \times 2 \times 6 + 5 \times 3 \times 6 = 126

本题要求运算次数最少,因此答案为 9090


对所有的数据,1n2×1061 \leq n \leq 2 \times 10^61w1041 \leq w \leq 10^4。其中:

  • 30%30\% 的数据,满足 n500n \leq 500
  • 对另外 30%30\% 的数据,满足 n2×105n \leq 2 \times 10^5