2241: 矩阵连乘
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：14
题目描述
题目描述
给定N个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?1<=N<=100，矩阵的行r[i]和列c[i]的范围：1<=r[i],c[i]<=100
输入描述
第一行有一个正整数N
接下来有N行，每行两个正整数，表示矩阵的行数和列数
保证本行的列数c[i]等于下一行的行数r[i+1]
输出描述
所需的最少乘法次数
样例输入 复制
3
10 100
100 5
5 50
样例输出 复制
7500