P1080 - 矩阵链排序问题

内存限制：512 MB 时间限制：1.500 S

评测方式：文本比较命题人：

提交：5 解决：4

给定 $lns="http://www.w3.org/1998/Math/MathML"> n$ 个矩阵，已知第 $lns="http://www.w3.org/1998/Math/MathML"> i$ 个矩阵 $lns="http://www.w3.org/1998/Math/MathML"> M_{i}$ 的大小为 $lns="http://www.w3.org/1998/Math/MathML"> w_{i}$ 行 $lns="http://www.w3.org/1998/Math/MathML"> w_{i + 1}$ 列，而我们并不关心其内容。我们考虑将其按照顺序相乘（称其为链乘积）：

$lns="http://www.w3.org/1998/Math/MathML" display="block"> M = M_{1} \times M_{2} \times \dots \times M_{n}$

矩阵乘法并不满足交换律，但是其满足结合律，因此我们可以通过合理安排结合顺序，尽可能减少需要的运算次数。在此题中，我们定义将一个大小为 $lns="http://www.w3.org/1998/Math/MathML"> a \times b$ 的矩阵乘以一个大小为 $lns="http://www.w3.org/1998/Math/MathML"> b \times c$ 的矩阵需要 $lns="http://www.w3.org/1998/Math/MathML"> a b c$ 次运算。

请你算出将题目所给的 $lns="http://www.w3.org/1998/Math/MathML"> n$ 个矩阵进行链乘积所需的最少运算数。为了方便起见，你不需要构造方案。

输入的第一行为一个正整数 $lns="http://www.w3.org/1998/Math/MathML"> n$ ，代表矩阵的数量。

接下来的一行包含 $lns="http://www.w3.org/1998/Math/MathML"> n + 1$ 个正整数，其中第 $lns="http://www.w3.org/1998/Math/MathML"> i$ 个整数为 $lns="http://www.w3.org/1998/Math/MathML"> w_{i}$ ，含义参考题目描述。

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

3
5 3 2 6

样例解释：样例告诉我们有 $lns="http://www.w3.org/1998/Math/MathML"> n = 3$ 个矩阵，其大小分别是 $lns="http://www.w3.org/1998/Math/MathML"> 5 \times 3$ ， $lns="http://www.w3.org/1998/Math/MathML"> 3 \times 2$ 和 $lns="http://www.w3.org/1998/Math/MathML"> 2 \times 6$ 。分别考虑两种乘法顺序：

先将 $lns="http://www.w3.org/1998/Math/MathML"> M_{1}$ 和 $lns="http://www.w3.org/1998/Math/MathML"> M_{2}$ 相乘得到一个 $lns="http://www.w3.org/1998/Math/MathML"> 5 \times 2$ 的矩阵，然后和 $lns="http://www.w3.org/1998/Math/MathML"> M_{3}$ 相乘，此时运算次数为 $lns="http://www.w3.org/1998/Math/MathML"> 5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$ ；
先将 $lns="http://www.w3.org/1998/Math/MathML"> M_{2}$ 和 $lns="http://www.w3.org/1998/Math/MathML"> M_{3}$ 相乘得到一个 $lns="http://www.w3.org/1998/Math/MathML"> 3 \times 6$ 的矩阵，然后和 $lns="http://www.w3.org/1998/Math/MathML"> M_{1}$ 相乘，此时运算次数为 $lns="http://www.w3.org/1998/Math/MathML"> 3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$ 。

本题要求运算次数最少，因此答案为 $lns="http://www.w3.org/1998/Math/MathML"> 90$ 。

对所有的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq n \leq 2 \times 1 0^{6}$ ， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq w \leq 1 0^{4}$ 。其中：

对 $lns="http://www.w3.org/1998/Math/MathML"> 30 %$ 的数据，满足 $lns="http://www.w3.org/1998/Math/MathML"> n \leq 500$ ；
对另外 $lns="http://www.w3.org/1998/Math/MathML"> 30 %$ 的数据，满足 $lns="http://www.w3.org/1998/Math/MathML"> n \leq 2 \times 1 0^{5}$ 。

提逝：本题数据较氵（绝对不是因为STAFF 懒的弄）, 暴力可打

动态规划区间dp

提交提交记录统计露一手!

1080: 矩阵链排序问题

题目描述

输入

输出

样例输入复制

样例输出复制

提示

来源/分类

1080: 矩阵链排序问题

题目描述

输入

输出

样例输入 复制

样例输出 复制

提示

来源/分类

样例输入复制

样例输出复制