Problem 1215 --用动态规划求解矩阵乘法链问题

1215: 用动态规划求解矩阵乘法链问题

上一题 正确率: $76.06\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $710$ 正确数量 $540$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划

Description

设矩阵A为100×1的矩阵，B为1×100矩阵，C为100×1的矩阵，则计算A×B的时间耗费为10000（由100×1×100得到），得到的结果D为100×100矩阵，再与C相乘所需的时间耗费为1000000，因此计算(A×B)×C的总时间1010000。B×C的时间耗费为10000，得到的中间矩阵为1×1矩阵，再与Ａ相乘的时间耗费为100，因而计算A×(B×C)的时间耗费只有10100。从上面的分析可以看的出不同的乘法顺序所耗费的时间是不同，甚至是相差很大的。现有一矩阵链M1×M2×M3×M4×M5×M6………，试问如何选择计算顺序才能使所耗费的时间最少。

Input

矩阵乘法链长度为N的问题其输入数据由N＋1行组成，第一行为矩阵乘法链的长度，即矩阵的个数。剩下的N行为N个矩阵的行列信息。每行的第一个元素是矩阵行数，第二个元素是矩阵的列数，元素之间以空格隔开。(2<=N<=1000)

Output

输出计算这个矩阵乘法链的最少耗费时间。

Sample Input复制

6
30 35
35 15
15 5
5 10
10 20 
20 25

Sample Output复制

15125

推荐代码 查看1215 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 安书杰 587337 2020-05-24 16:42:30
内存最少[$0 $KB] HSDYND 613873 2020-10-03 15:31:29
第一AC AOJ大管家 10608 2016-09-08 20:51:41
第一挑战 AOJ大管家 10595 2016-09-08 20:42:13

赛题来源/所属竞赛 NA N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1800 2023-2024-2学期<计算机专业竞赛实训> 第4周练习：递推和动态规划【22计算机】 2024-03-18 00:00:00 请登录
1740 2022-2023-2学期<计算机专业竞赛实训> 第6周练习：递推和动态规划【21计算机12345】 2023-03-27 00:00:00 请登录
1685 2021-2022-2学期<算法分析与设计> 第6周练习：递推和动态规划 2022-03-28 00:00:00 请登录
1612 2020-2021-2学期<算法分析与设计> 第10周练习：递推和动态规划 2021-04-19 08:00:00 请登录
1587 2020《图灵信息学算法》高级班第5单元:动态规划 2020-11-01 10:00:00 请登录