题目传送门
1 /*
2 题意：加上适当的括号，改变计算顺序使得总的计算次数最少
3 矩阵连乘积问题，DP解决：状态转移方程：
4 dp[i][j] = min (dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]) (i<=k<j)
5 s[i][j] 记录断开的地方(即加括号的位置)，回溯法输出结果
6 */
7 #include <cstdio>
8 #include <cstring>
9 #include <string>
10 #include <algorithm>
11 #include <cmath>
12 #include <iostream>
13 using namespace std;
14
15 const int MAXN = 1e2 + 10;
16 const int INF = 0x3f3f3f3f;
17 int dp[MAXN][MAXN];
18 int s[MAXN][MAXN];
19 int p[MAXN];
20 int n;
21
22 void print(int i, int j)
23 {
24 if (i == j) printf ("A%d", i);
25 else
26 {
27 printf ("(");
28 print (i, s[i][j]);
29 printf (" x ");
30 print (s[i][j] + 1, j);
31 printf (")");
32 }
33 }
34
35 void work(void)
36 {
37 for (int i=1; i<=n; ++i) dp[i][i] = 0;
38 for (int l=2; l<=n; ++l)
39 {
40 for (int i=1; i<=n-l+1; ++i)
41 {
42 int j = i + l - 1;
43 dp[i][j] = INF;
44 for (int k=i; k<=j-1; ++k)
45 {
46 int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];
47 if (tmp < dp[i][j])
48 {
49 dp[i][j] = tmp; s[i][j] = k;
50 }
51 }
52 }
53 }
54
55 print (1, n); puts ("");
56 }
57
58 int main(void) //ZOJ 1276 Optimal Array Multiplication Sequence
59 {
60 //freopen ("ZOJ_1276.in", "r", stdin);
61
62 int cas = 0;
63 while (scanf ("%d", &n) == 1)
64 {
65 if (n == 0) break;
66 for (int i=1; i<=n; ++i) scanf ("%d%d", &p[i-1], &p[i]);
67
68 printf ("Case %d: ", ++cas);
69 work ();
70 }
71
72 return 0;
73 }
74
75 /*
76 Case 1: (A1 x (A2 x A3))
77 Case 2: ((A1 x A2) x A3)
78 Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
79 */