题目传送门

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
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           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 else26 {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 Sequence59 {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 */