Problem 2683 --Dynamic Programming - Matrix Chain Multiplication

2683: Dynamic Programming - Matrix Chain Multiplication

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

Description

Matrix-chain Multiplication 

The goal of the matrix-chain multiplication problem is to find the most efficient way to multiply given n matrices M1,M2,M3,...,Mn. Write a program which reads dimensions of Mi, and finds the minimum number of scalar multiplications to compute the maxrix-chain multiplication M1M2...Mn.

Input

In the first line, an integer n is given. In the following n lines, the dimension of matrix Mi (i=1...n) is given by two integers r and cc which respectively represents the number of rows and columns of Mi.

Output

Print the minimum number of scalar multiplication in a line.

Sample Input复制

6
30 35
35 15
15 5
5 10
10 20
20 25

Sample Output复制

15125

提示

1≤ n≤ 100

1≤ r,c≤ 100

推荐代码 查看2683 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛