矩阵链相乘实例

题目描述

零崎有很多朋友，其中有一个叫jhljx。

jhljx大家很熟悉了，他数学不好也是出了名的，大家都懂。

现在jhljx遇到了矩阵乘法，他当时就懵了。数都数不清的他，矩阵乘法怎么可能会算的清楚呢？虽然零崎觉得还不如让你们来算，不过好歹也要给jhljx个面子，给她留下一个证明自己数学实力的机会。为了减小jhljx的计算量，让他赶快算出不正确答案来（估计他算上几遍都不一定能出一个正确答案），零崎请你们帮助jhljx。

输入

多组输入数据。

每组数据以N开始，表示矩阵链的长度。接下来一行N+1个数表示矩阵的行/列数。

1<=N<=300

输出

对于每组样例，输出一行最少运算次数的方案，每两个矩阵相乘都用“()”括起来，详见样例

如果存在多种解决方案,最终输出结果选取先计算左边的矩阵，详见Hint

输入样例

输出样例

((A1A2)A3)
((A1A2)A3)

Hint

对于输入的第二组数据,

如果计算顺序为((A1A2)A3)，结果为10×20×5 + 10×5×4= 1200,

如果计算顺序为A1(A2A3), 结果为20×5×4 + 10×20×4 = 1200

那么输出结果选取第一个

题目来源：http://biancheng.love/contest/17/problem/D/index

题目注意事项：如果存在多种解决方案,最终输出结果选取先计算左边的矩阵

下面给出实现代码：

 1 #include <bits/stdc++.h>
 2 #define max_size 400
 3 #define INF 100000000
 4 long long s[max_size][max_size];//保存构造最优解信息
 5 long long p[max_size];//矩阵规模的记录
 6 long long m[max_size][max_size];//记录最优值
 7 
 8 void  matrix_chain_order(int n)
 9 {
10     for(int i=1;i<=n;i++)
11     {
12         m[i][i]=0;//初始化最优值(起始于1,结束于n)
13     }
14     for(int l=2;l<=n;l++)//l表示矩阵的长度
15     {
16         for(int i=1;i<=n-l+1;i++)
17         {
18             int j=i+l-1;
19             m[i][j]=INF;
20             s[i][j]=0;
21             for(int k=j-1;k>=i;k--)//解决方案优先选取先左边的矩阵
22             {
23                 int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
24                 if(q<m[i][j])
25                 {
26                     m[i][j]=q;
27                     s[i][j]=k;
28                 }
29             }
30         }
31     }
32 }
33 
34 void print_optimal_parents(int i,int j)//打印最优解的结果
35 {
36     if(i==j)
37         printf("A%d",i);
38     else
39     {
40             printf("(");
41             print_optimal_parents(i,s[i][j]);
42             print_optimal_parents(s[i][j]+1,j);
43             printf(")");
44     }
45 }
46 
47 int main()
48 {
49     int n;
50     while(~scanf("%d",&n))
51     {
52         memset(p,0,sizeof(p));
53         for(int i=0;i<=n;i++)
54         {
55             scanf("%lld",&p[i]);
56         }
57         matrix_chain_order(n);
58         print_optimal_parents(1,n);
59         printf("
");
60     }
61 }

对实现过程的详细解答请见http://www.cnblogs.com/Anker/archive/2013/03/10/2952475.html