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

上一题 正确率: $76.20\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $710$ 正确数量 $541$
裁判形式 标准裁判/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