问题 3207 --矩阵连乘

3207: 矩阵连乘

题目描述

  墨老师:“其实大家要学会学习,而不只是死记硬背,例如爱恩斯坦曾经说过:‘我从来不记在辞典上已经印着的东西,我的记忆力是用来记忆书本上没有的东西。’”
楚继光如释重负:“老师,我明白了,接下来你要讲的矩阵乘法,我终于可以不记了。”
墨老师:“呃,这个知识点,你还是要记的。”
矩阵乘法是线性代数中最基础的一个知识点,设矩阵A为一个n行m列的矩阵,矩阵B为x行y列,那么A能乘B的条件为m = x,它们相乘将得出一个n行y列的矩阵,进行一次矩阵乘法的运算次数为n×m×y,现在给出k个矩阵,你每次可以合并相邻的两个矩阵,将它们做乘法得出的矩阵作为合并的结果,请问如何合并能使得总的运算次数最少。


输入

       接下来k(K<=25)行,每行两个正整数表示该矩阵的行和列 (每个数≤50)。

输出

       一个整数表示最少的合并代价。

样例输入输出

输入#1 复制
3
1 5
5 20
20 1
输出#1 复制
105

提示

序号 标题 作者 发表时间 费用 订购数 操作