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

/*recursive method*/
int rec_min(int *dim, int n, int r, int s){
  if(r == s)
    return 0;
  int min, t, c_t;
  min = rec_min(dim,n,r+1,s)+dim[r]*dim[r+1]*dim[r+1]*dim[s+1];
  for(t=r+1; t<s; t++){
    c_t = rec_min(dim,n,r,t)+rec_min(dim,n,t+1,s)+dim[r]*dim[t+1]*dim[t+1]*dim[s+1];
    if (c_t < min)
      min = c_t;
  }
  return min;
}

/*efficient method*/
int dp_min(int **split, int *dim, int n){
  int **cost;  //cost[i][j] stores minimum cost of multiplying A_i through A_j 
  
  int r, s, t, k, min, c_t;
  
  cost = (int **)malloc(n*sizeof(int*));

  for(r=0; r<n; r++)
    cost[r] = (int *)malloc(n*sizeof(int));

  for(r=0; r<n; r++)
      cost[r][r] = 0;
 
  for(s=1; s<n; s++){
    for(r=0; r<n-s; r++){
      k = r+s;
      min = cost[r][r]+cost[r+1][k]+dim[r]*dim[r+1]*dim[r+1]*dim[k+1];
      split[r][k] = r;
      for(t=r+1; t<k; t++){
	c_t = cost[r][t]+cost[t+1][k]+dim[r]*dim[t+1]*dim[t+1]*dim[k+1];
	if(c_t < min){
	  min = c_t;
	  split[r][k] = t;
	}
      }
      cost[r][k] = min;
    }
  }
  return cost[0][n-1];
}

void print_order(int r, int s, int **split){
  if(r == s){
    printf("A_%d",r+1);
    return;
  }

  printf("(");
  print_order(r,split[r][s],split);
  print_order(split[r][s]+1,s,split);
  printf(")");
}

int main(){
  int *dim, n;
  printf("\nn = ");
  scanf("%d", &n);
  dim = (int *)malloc((n+1)*sizeof(int));
  printf("Dimensions: ");
  int i;
  for(i=0; i<=n; i++)
    scanf("%d", &dim[i]);

  int **split; //split[i][j] stores splitting point acheiving the minimum cost
  split = (int **)malloc(n*sizeof(int*));
  for(i=0; i<n; i++)
    split[i] = (int *)malloc(n*sizeof(int));

  int min_cost;

  printf("\nRecursive Method\n");
  clock_t start = clock();
  min_cost = rec_min(dim,n,0,n-1);
  clock_t end = clock();
  printf("--Minimum cost = %d\n",min_cost);
  printf("--Time spent = %.6f seconds\n\n",((double)(end-start)/CLOCKS_PER_SEC));

  printf("\nEfficient Method\n");
  start = clock();
  min_cost = dp_min(split,dim,n);
  end = clock();
  printf("--Minimum cost = %d\n",min_cost);
  printf("--Time spent = %.6f seconds\n\n",((double)(end-start)/CLOCKS_PER_SEC));
  printf("--Optimal grouping: ");
  print_order(0,n-1,split);
  printf("\n\n");
return 0;
}