/*
 * Pierre Hyvernat, exemple de programme pour le TP1 du cours info803.  C'est
 * presque une correction...
 *
 * On cherche le parenthésage minimisant le nombre de multiplications
 * scalaires pour le calcul du produit d'une chaîne de matrices...
 * (exemple typique de progrqmmqtion dynamique)
 */


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



/* variables globales :
 *   - n est le nombre de matrices à multiplier
 *   - T est le tableau des tailles des matrices
 *   - M est le tableau qui contient le nombre optimal de multiplications pour
 *     multiplier des sous-chaînes
 *   - P est le tableau qui contient les indices des endroits où il faut
 *     couper pour multiplier des sous-chaînes
 *
 * Pour gagner de la place (?); on pourrait en fait utiliser un seul tableau
 * au lieu de M et P : on utiliserait la partie au dessus de la diagonale pour
 * M et la partie au dessous de la diagonale pour P...
 */
int n, *T, **M, **P;



/*
 * fonction d'affichage du parenthésage contenu dans le tableau P.
 * le booléen b sert à omettre les parenthéses externes...
 */
void affiche(int i, int j, int b) {
 int k ;
 if (i==j) printf("M") ;
 else {
  k = P[i][j] - 1 ;
  if (b) printf("(") ;
  affiche(i, k, 1) ;
  printf(" x ");
  affiche(k+1,j, 1);
  if (b) printf(")") ;
 }
}



/*
 * la fonction principale, qui fait tout...
 */
int main () {

int i,j,k,tmp,N,d,t ;


/* lecture du tableau des tailles */
printf("Combien de matrices voulez-vous multiplier ?    ");
if (scanf("%i",&n)!=1) { printf("??? Il fallait me donner un entier...\n") ; return(-1) ;}

T = malloc ((n+1)*sizeof(int)) ;

printf("Quelles sont les tailles des matrices ?\n");

for(i=0;i<=n;i++) {
 printf("t(%i) = ?    ",i) ;
 if (scanf("%i",T+i)!=1) { printf("??? Il fallait me donner un entier...\n") ; return(-1) ;}
}


printf("\n\nOn veut multiplier des matrices de tailles :\n") ;
for(i=0;i<n;i++) printf("  %i x %i\n",T[i],T[i+1]) ;


/* Initialisation des tableaux de données. */
// printf("Initialisation des tableaux de données...\n") ;
M = malloc (n*sizeof(int*)) ;
P = malloc (n*sizeof(int*)) ;

for(i=0;i<n;i++) {
 M[i]=malloc (n*sizeof(int)) ;   /* c'est un peu le bazar car M et P sont */
 P[i]=malloc (n*sizeof(int)) ;   /* des tableaux à deux dimensions... */
}

for(i=0;i<n;i++) for(j=0;j<n;j++) {
 M[i][j]=0 ;
 P[i][j]=0;
}



/* Remplissage des tableaux. */
for(d=1;d<n;d++) {    /* numero de la diagonale */
 for(t=0;t<n-d;t++) {  /* numero d'élément dans la diagonale */

  i = t ;     /* ligne courante */
  j = t+d ;   /* colonne courante */


  N=T[i]*T[j+1] ;  /* tailles extremales pour la multiplication de i à j */


  /* premiere valeur de k, pour initialiser le minimum... */
  M[i][j] =  M[i][i] + M[i+1][j] + N*T[i+1] ;
  P[i][j] = i+1 ;

  /* recherche de la coupure (k) qui minimise le nombre de multiplications */
  for(k=i+1;k<j;k++) {
   tmp = M[i][k] + M[k+1][j] + N*T[k+1] ;
   if(tmp < M[i][j]) {
    P[i][j] = k+1 ;
    M[i][j] = tmp ;
   }
  }
 }
}




/* affichage des tableaux calculés... */
printf("Tableau M :\n") ;
for (i=0;i<n;i++) {
 for (j=0;j<n;j++) {
  printf("%8i  ",M[i][j]);
 }
 printf("\n");
}

printf("Tableau P :\n") ;
for (i=0;i<n;i++) {
 for (j=0;j<n;j++) {
  printf("%2i  ",P[i][j]);
 }
 printf("\n");
}


/* affichage du parenthésage optimal */
printf("Le nombre minimal de multiplication scalaires pour multiplier une telle chaîne est %i.\n",M[0][n-1]);
printf("Un parenthésage optimal est donné par : \n    ");
affiche(0,n-1,0) ;
printf("\n") ;

return(1) ;

}