Matrix Chain Multiplication : UVA -> 348

#include<stdio.h>
#define INF 999999999
#define sz 12


int m[sz][sz], s[sz][sz], temp ;


int Matrix_chain_multiplication( int p[], int n )
{
int i, j, k, l ;


for(i=0;i<=n;i++) m[i][i] = 0 ;


for(l=2;l<=n;l++)
{
for(i =1; i<=n-l+1; i++ )
{
j = i+l-1;
m[i][j] = INF ;
for(k=i;k<=j-1;k++)
{
temp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] ;
if( temp<m[i][j] )
{
m[i][j] = temp ;
s[i][j] = k;
}
}
}
}
return m[1][n];
}


void Print_parenthesis( int s[][sz], int i, int j )
{
if( i==j )
printf("A%d",i);


else
{
printf("(");
Print_parenthesis( s, i, s[i][j] );


printf(" x ");
Print_parenthesis( s, s[i][j]+1, j );
printf(")");
}
}


int main(void)
{
int p[sz+1], i, j, n, tcase = 0 ;


while( scanf("%d",&n)==1 &&n )
{
for(i=0;i<n;)
{
scanf("%d",&p[i++]);
scanf("%d",&p[i]);
}
printf("Case %d: ",++tcase);


        printf("total cost: %ld\n", Matrix_chain_multiplication(p, n));
Print_parenthesis(s, 1, n );
printf("\n");
}


return 0;
}
/*
Input:
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25


Output:
Case 1: total cost: 105
(A1 x (A2 x A3))
Case 2: total cost: 4500
((A1 x A2) x A3)
Case 3: total cost: 15125
((A1 x (A2 x A3)) x ((A4 x A5) x A6))
*/