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

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $994$ 正确数量 $541$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
设矩阵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矩阵,再与A相乘的时间耗费为100,因而计算A×(B×C)的时间耗费只有10100。从上面的分析可以看的出不同的乘法顺序所耗费的时间是不同,甚至是相差很大的。现有一矩阵链M1×M2×M3×M4×M5×M6………,试问如何选择计算顺序才能使所耗费的时间最少。

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

输出计算这个矩阵乘法链的最少耗费时间。
6
30 35
35 15
15 5
5 10
10 20 
20 25
15125