Follows 348.c (Total 50 lines):

/* @JUDGE_ID:4461XX 348 C */
/* A */
#include<stdio.h>
struct ma{
	int m ;
	int n ;
	long step ;
	int kk ;
}ma[10][10] ;
int n ;
void trace_back( int begin , int end )
{
	if( begin == end )
		printf( "A%d" , begin+1 ) ;
	else{
		putchar( '(' ) ;
		trace_back( begin , ma[begin][end].kk ) ;
		printf( " x " ) ;
		trace_back( ma[begin][end].kk+1 , end ) ;
		putchar( ')' ) ;
	}
}
void main( void )
{
	int i , j , l , k ;
	long min ;
	for( i=1 ; ; i++ ){
		scanf( "%d" , &n ) ;
		if( !n ) break ;
		for( j=0 ; j<n ; j++ ){
			for( l=j ; l<n ; l++ ) ma[j][l].step = 0 ;
			scanf( "%d %d" , &ma[j][j].m , &ma[j][j].n ) ;
			ma[j][j].kk = j ;
		}
		for( j=n-2 ; j>=0 ; j-- )
			for( l=j+1 ; l<n ; l++ )
				for( k=j ; k<l ; k++ ){
					min = ma[j][k].step + ma[k+1][l].step + ma[j][k].m*ma[j][k].n*ma[k+1][l].n ;
					if( !ma[j][l].step || min <= ma[j][l].step ){
						ma[j][l].step = min ;
						ma[j][l].m = ma[j][k].m ;
						ma[j][l].n = ma[k+1][l].n ;
						ma[j][l].kk = k ;
					}
				}
		printf( "Case %d: " , i ) ;
		trace_back( 0 , n-1 ) ;
		putchar( '\n' ) ;
	}
}

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com