C3-Zexal的矩阵链乘

题目描述

用加括号的方式给出最优的矩阵相乘方案

输入

多组数据输入

第一行一个整数 $n$

接下来一行 $n + 1$

别问我为什么只有n+1个数，每相邻的两个数表示一个矩阵的大小

输出

对于每组数据，输出两行，第一行为计算次数，第二行为计算方案，用加括号的方式给出最优的矩阵相乘方案

如果不幸最优方案不唯一，选择优先计算左边的矩阵

输入样例

输出样例

4500
((A1A2)A3)
1200
((A1A2)A3)

Hint

在第二组样例中，选择((A1A2)A3)时，结果为10×20×5+10×5×4=1200

选择A1(A2A3)时，结果为20×5×4 + 10×20×4 = 1200

这时选择第一种，优先计算左边的！

代码

 1 #include <iostream>
 2 #include <iomanip>
 3 #include <cstring>
 4 #define N 1005
 5 using namespace std;
 6 typedef int T;
 7 T m[N][N],s[N][N],p[N];
 8 void PRINT_OPTIMAL_PARENS(int i, int j)
 9 {
10     if(i == j) cout<<"A"<<i;
11     else
12     {
13         cout<<"(";
14         PRINT_OPTIMAL_PARENS(i,s[i][j]);
15         PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
16         cout<<")";
17     }
18 }
19 void MATRIX_CHAIN_ORDER( T p[] , int n)
20 {
21     for(int i  = 1; i <= n; i++) m[i][i] = 0;
22     for(int l = 2; l <= n; l++)
23     {
24         for(int i = 1 ; i <= n - l +1 ; i++)
25         {
26             int j = i + l - 1;
27             m[i][j] = 0x3F3F3F3F;
28             for(int k = i; k <= j-1 ; k++)
29             {
30                 int q = m[i][k]+m[k+1][j]+ p[i-1]*p[k]*p[j];
31                 if(m[i][j] >= q)
32                 {
33                     m[i][j] = q;
34                     s[i][j] = k;
35                 }
36             }
37         }
38     }
39     cout <<m[1][n] <<endl;
40     PRINT_OPTIMAL_PARENS(1,n);
41 }
42 
43 int main()
44 {
45     ios::sync_with_stdio(false);
46     int x;
47     while(cin>>x)
48     {
49         memset(p,0,sizeof(p));
50         memset(m,0,sizeof(m));
51         memset(s,0,sizeof(s));
52         for(int i = 0; i <= x; i++) cin>>p[i];
53         MATRIX_CHAIN_ORDER(p,x);
54         cout<<endl;
55     }
56 
57     return 0;
58 }