#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXDIM 1000
#define INFINITY 1000000000

void genDimen ( int D[], int n )
{
   int i;

   for (i=0; i<=n; ++i) D[i] = 1 + rand() % 9;
   printf("Dimensions are: ");
   for (i=0; i<n; ++i) printf("%dx%d ", D[i], D[i+1]);
   printf("\n");
}

int C ( int D[], int i, int j )
{
   int k, min, m, m1, m2;

   if (j <= i+1) return 0;
   min = INFINITY;
   for (k=i+1; k<=j-1; ++k) {
      m1 = C(D,i,k);
      m2 = C(D,k,j);
      m = m1 + m2 + D[i] * D[k] * D[j];
      if (m < min) min = m;
   }
   return min;
}

int main ()
{
   int D[MAXDIM], n, m;

   srand((unsigned int)time(NULL));
   printf("How many matrices? "); scanf("%d", &n);
   if ((n < 0) || (n >= MAXDIM)) {
      fprintf(stderr, "Invalid number of matrices\n");
      exit(1);
   }
   genDimen(D,n);
   m = C(D,0,n);
   printf("Minimum effort is %d\n", m);
   exit(0);
}