题目描述

给定N个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少?矩阵的行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