题目名称	1136. 最优矩阵链乘
输入输出	`goodmatrix.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	5
题目来源	Makazeu 于2012-10-10加入
开放分组	全部用户
提交状态
分类标签	动态规划合并类动态规划
	分享题解

通过：111，提交：199，通过率：55.78%
可以的.	100	0.000 s	0.00 MiB	C++
LOSER	100	0.000 s	0.00 MiB	C++
SOBER GOOD BOY	100	0.000 s	0.00 MiB	C++
SOBER GOOD BOY	100	0.000 s	0.00 MiB	C++
面对疾风吧疾风疾风吧	100	0.000 s	0.00 MiB	C++
_Itachi	100	0.000 s	0.00 MiB	C++
【离开·再见】星裔·自由蒂兰	100	0.000 s	0.00 MiB	C++
半汪	100	0.000 s	0.00 MiB	C++
dateri	100	0.000 s	0.00 MiB	C++
cy	100	0.000 s	0.00 MiB	C++

关于最优矩阵链乘的近10条评论(全部评论)
上一次交登错号了.... Fisher. 2017-09-18 20:57 8楼
AntiLeaf 2017-05-25 15:50 7楼
题意有毒啊，好好的一个区间dp。。。连着WA了两次，原因竟然是inf选得不够大............................. sxysxy 2016-12-22 17:31 6楼
样例怎么得到的64？我怎么算也不是64啊 iortheir 2016-09-04 16:28 5楼
这题的数据用int不会爆 liu_runda 2016-03-24 12:25 4楼
75题斩纪念 YGOI_真神名曰驴蛋蛋 2016-03-24 11:42 3楼
吐槽下错别字= =....应该是链乘吧。。另外分类里强连通分量QAQ..... raywzy 2013-09-24 12:50 2楼
好几个地方的控制变量是试出来的，根据对称性什么的。 Truth.Cirno 2012-10-13 17:48 1楼

1136. 最优矩阵链乘

★★ 输入文件：goodmatrix.in 输出文件：goodmatrix.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵，运算量为nmp。
矩阵乘法满足结合律，A*B*C可以表示成(A*B)*C或者是A*(B*C)，两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时，(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
现在给出N个矩阵，并输入N+1个数，第i个矩阵是a[i-1]*a[i]

【输入格式】

第一行n(n<=100)
第二行n+1个数

【输出格式】

最优的运算量

【样例输入】

3
2 3 4 5

【样例输出】

【来源】

算法竞赛入门经典例题 9-6