POJ1651Multiplication Puzzle（矩阵链乘变形）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int Max = 100 + 5;
 7 const int INF = 0x3f3f3f3f;
 8 int dp[Max][Max],card[Max];
 9 int n;
10 void Input()
11 {
12     for(int i = 1; i <= n; i++)
13         scanf("%d", &card[i]);
14 }
15 int solve()
16 {
17     memset(dp, 0, sizeof(dp));
18     for(int p = 2; p < n; p++)
19     {
20         for(int i = 1; i < n; i++)
21         {
22             int j = i + p;
23             if(j > n)
24                 break;
25             dp[i][j] = INF;
26             for(int k = i + 1; k < j; k++)
27             {
28                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + card[i] * card[k] * card[j]);
29             }
30         }
31     }
32     return 0;
33 }
34 int main()
35 {
36     while(scanf("%d", &n) != EOF)
37     {
38         Input();
39         solve();
40         printf("%d\n", dp[1][n]);
41     }
42     return 0;
43 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int Max = 100 + 5;
 7 const int INF = 0x3f3f3f3f;
 8 int dp[Max][Max],card[Max],trace[Max][Max]; //记录选择方案
 9 int n;
10 void Input()
11 {
12     for(int i = 1; i <= n; i++)
13         scanf("%d", &card[i]);
14 }
15 int solve()
16 {
17     memset(dp, 0, sizeof(dp));
18     memset(trace, 0, sizeof(trace));
19     for(int p = 2; p < n; p++)
20     {
21         for(int i = 1; i < n; i++)
22         {
23             int j = i + p;
24             if(j > n)
25                 break;
26             dp[i][j] = INF;
27             for(int k = i + 1; k < j; k++)
28             {
29                 if(dp[i][j] > dp[i][k] + dp[k][j] + card[i] * card[k] * card[j])
30                 {
31                     dp[i][j] =  dp[i][k] + dp[k][j] + card[i] * card[k] * card[j];
32                     trace[i][j] = k;
33                 }
34             }
35         }
36     }
37     return 0;
38 }
39 void print(int Begin, int End)
40 {
41     if(End - Begin <= 1)
42         return ;
43     printf("%d ", trace[Begin][End]);  //结果是逆序的
44     print(Begin, trace[Begin][End]);
45     print(trace[Begin][End], End);
46 }
47 int main()
48 {
49     while(scanf("%d", &n) != EOF)
50     {
51         Input();
52         solve();
53         printf("%d\n", dp[1][n]);
54         print(1,n);
55     }
56     return 0;
57 }