算法题1 矩阵连乘问题

发布时间: 2017年6月19日 00:23   时间限制: 1000ms   内存限制: 128M

给定n个矩阵A1A2…,An,其中,AiAj+1是可乘的,i=1,2,…,n-1。

你的任务是要确定矩阵连乘的运算次序,使计算这n个矩阵的连乘积A1A2An总的元素乘法次数达到最少。

例如:3个矩阵A1A2A3,阶分别为10×100、100×5、5×50,计算连乘积A1A2A3时按(A1A2A3所需的元素乘法次数达到最少,为7500次。

测试数据有若干组,每组测试数据有2行。

每组测试数据的第1行是一个整数n,(0<n<20),第2行是n+1个正整数p0、p1、p2、…、pn,这些整数不超过100,相邻两个整数之间空一格,他们表示n个矩阵A1A2…,An,的阶pi-1´pi,i=1,2,…,n。

输入直到文件结束。

对输入中的每组测试数据,输出2行。先在一行上输出“Case #”,其中“#”是测试数据的组号(从1开始),再在第2行上输出计算这n个矩阵的连乘积A1A2An时最少的总的元素乘法次数,再空一格,接着在同一行上输出矩阵连乘的添括号形式。

注意:最外层括号应去掉。

复制
3
10 100 5 50
4
50 10 40 30 5
Case 1
7500 (A1A2)A3
Case 2
10500 A1(A2(A3A4))
1611

old_judge

算法