PID652 / 矩阵链乘法
题目描述

我们都知道矩阵乘法:给定两个矩阵A和B,若A是n*r的矩阵,B是r*m的矩阵,则A*B的结果C是一个n*m的矩阵,且c[i,j]=∑a[i,k]*b[k,j],其中1<=k<=r。很显然,求出每个C[i,j]的过程中,我们都做了r次标量乘法。因此,总的标量乘法次数是n*m*r。

矩阵乘法满足结合律。换句话说,即使乘的顺序不同,结果都是相同的。例如,四个矩阵<A1,A2,A3,A4>相乘,会有五种不同的顺序:

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

((A1(A2A3))A4)

(((A1A2)A3)A4)

但是,不同的顺序会导致不同的效率——本题中,我们希望将给定的矩阵乘起来,并且使得总的标量乘法次数最少。注意,本题中给定的矩阵可以看作是环形的——第一个和最后一个矩阵可以相乘!为了满足矩阵乘法的合法性,输入数据保证对于任意相邻的矩阵,它们相邻的维数一定相等。

【数据规模和约定】

n<=100

所有矩阵的行、列数都是不超过1000的正整数。

输入格式

第一行一个整数n,表示矩阵个数。

接下来n行,每行两个整数,表示这个矩阵的行数和列数。

输出格式

一个整数,表示最少乘法次数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论