零崎的朋友很多Ⅲ

时间限制: 1000 ms 内存限制: 65536 kb

总通过人数: 173 总提交人数: 194

题目描述

零崎有很多朋友，其中有一个叫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

那么输出结果选取第一个

Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 303
 4 #define Min 1000000000
 5 void Matrix_Chain_Order(int p[],int n);
 6 void Print_Optimal_Parens(int i,int j);
 7 int s[M][M];
 8 int main()
 9 {
10     int n;
11     while(scanf("%d",&n) == 1){
12         int p[M];
13         memset(p,'0',M);
14         int i;
15         for(i = 0;i <= n;i++)
16             scanf("%d",&p[i]);
17         Matrix_Chain_Order(p,n);
18     }
19 
20     return 0;
21 }
22 
23 void Matrix_Chain_Order(int p[],int n)
24 {
25     int m[n+1][n+1];
26     //边界条件
27     int i,j;
28     for(i = 1;i <= n;i++)
29         m[i][i] = 0;
30     //计算每个子问题m[i,j]的解
31     int l;
32     for(l = 2;l <= n;l++){
33         for(i = 1;i <= n-l+1;i++){
34             j = i + l - 1;
35             m[i][j] = Min;
36             int k;
37             for(k = i;k <= j-1;k++){
38                 int val;
39                 val = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
40                 if(m[i][j] >= val){//“>=”！！！！！！不能少等号不然顺序就不对了我也不知大为什么！！！！！！！
41                     m[i][j] = val;
42                     s[i][j] = k;
43                 }
44             }
45         }
46     }
47     Print_Optimal_Parens(1,n);
48     printf("\n");
49 }
50 void Print_Optimal_Parens(int i,int j)
51 {
52     if(i == j)
53         printf("A%d",i);
54     else{
55         printf("(");
56         Print_Optimal_Parens(i,s[i][j]);
57         Print_Optimal_Parens(s[i][j]+1,j);
58         printf(")");
59     }
60 }

C-Code-Print

Source

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_10_B

Description

Time Limit : 1 sec , Memory Limit : 131072 KB

Matrix-chain Multiplication

The goal of the matrix-chain multiplication problem is to find the most efficient way to multiply given $n$

Write a program which reads dimensions of $M_{i}$

Input

In the first line, an integer $n$

Output

Print the minimum number of scalar multiplication in a line.

Constraints

$1 \leq n \leq 100$
$1 \leq r, c \leq 100$

Sample Input 1

Sample Output 1

15125

Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 103
 4 #define Min 1000000000
 5 void Matrix_Chain_Order(int p[],int n);
 6 int main()
 7 {
 8     int n;
 9     while(scanf("%d",&n) == 1){
10         int p[M];
11         memset(p,'0',M);
12         int i;
13         for(i = 0;i < n;i++)
14             scanf("%d%d",&p[i],&p[i+1]);
15         Matrix_Chain_Order(p,n);
16     }
17 
18     return 0;
19 }
20 
21 void Matrix_Chain_Order(int p[],int n)
22 {
23     int m[n+1][n+1],s[n+1][n+1];
24     //边界条件
25     int i,j;
26     for(i = 1;i <= n;i++)
27         m[i][i] = 0;
28     //计算每个子问题m[i,j]的解 m[i,j]表示计算Ai,..,j的所需乘法次数的最小值
29     int l;
30     for(l = 2;l <= n;l++){//l:矩阵链的长度
31         for(i = 1;i <= n-l+1;i++){//i:当前l长的开头
32             j = i + l - 1;//j:当前l长的结尾
33             m[i][j] = Min;
34             int k;//k:划分点 在矩阵Ak后面拦一刀
35             for(k = i;k <= j-1;k++){
36                 int val;
37                 val = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
38                 if(m[i][j] > val){
39                     m[i][j] = val;
40                     s[i][j] = k;//s[i][j]:记录Ai,Aj间的划分点在Ak后面
41                 }
42             }
43         }
44     }
45     printf("%d\n",m[1][n]);
46 }

C-Code-Order