/* 矩阵连乘，区间动态规划 */

/*

 状态：DP[ l ][ s ] ——以 s 开始长度为 l 的区间的 矩阵乘积的最小值

 阶段：区间长度

 决策：DP[ l ][ s ] = min( DP[ k ][ s ] + DP[ l-k ][ s+k ] + 乘法代价 ) {1<k<l}

*/

1 #include 
      
         2 #include 
       
          3 #include 
        
           4  5 using namespace std;  6  7 struct node  8 {
      9     int R,C; 10 }X[ 11 ]; 11 12 int DP[ 11 ][ 12 ]; 13 int DI[ 11 ][ 12 ]; 14 15 void print( int l, int s ) 16 {
     17     if ( l > 1 ) {
     18         cout << "("; 19         print( DI[ l ][ s ], s ); 20         cout << " x "; 21         print( l-DI[ l ][ s ], s+DI[ l ][ s ] ); 22         cout << ")"; 23     }else cout << "A" << s; 24 } 25 26 int main() 27 {
     28     int n,t = 1; 29     while ( cin >> n && n ) {
     30         for ( int i = 1 ; i <= n ; ++ i ) 31             cin >> X[ i ].R >> X[ i ].C; 32         33         memset( DP, 0, sizeof( DP ) ); 34         for ( int l = 2 ; l <= n ; ++ l ) 35         for ( int s = 1 ; s+l-1 <= n ; ++ s ) {
     36             DP[ l ][ s ] = 0xffffff; 37             for ( int k = 1 ; k < l ; ++ k ) {
     38                 int Temp = DP[ k ][ s ] + DP[ l-k ][ s+k ] + X[ s ].R*X[ s+k ].R*X[ s+l-1 ].C; 39                 if ( DP[ l ][ s ] > Temp ) {
     40                     DP[ l ][ s ] = Temp; 41                     DI[ l ][ s ] = k; 42                 } 43             } 44         } 45         //cout << DP[ n ][ 1 ] << endl; 46         cout << "Case " << t ++ << ": "; 47         print( n, 1 ); 48         cout << endl; 49     } 50 }