UVA_348_Optimal_Matrix_Multiplication

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <limits.h>
#include <stdlib.h>
#include <cmath>
#define LL unsigned long long
using namespace std;
int n;
typedef struct m{
         int r;
        int c;
}Tmat;
Tmat arr[15];int s[15][15]; int B[15][15];
int cont=1;
int Imprimir(int i,int j){
    int aux=s[i][j];
    if(i==j){
        printf("A%d",i);
    }else{
        printf("(");Imprimir(i,aux);printf(" x ");

        Imprimir(aux+1,j);
        printf(")");
    }

}
int main() {
    int j;int q;int aux;int r,c;
     while(scanf("%d",&n)){
        if(n==0) break;
        for(int i=1;i<=n;i++){
            scanf("%d %d",&r,&c);
            arr[i].r=r;arr[i].c=c;

        }

        memset(s,0,sizeof(s[0][0])*15*15);
        memset(B,0,sizeof(B[0][0])*15*15);

        for (int i=1;i<=n;i++){
            B[i][i]=0;
        }
        for (int l=2;l<=n;l++){
            for(int i=1;i<=n-l+1;i++){
                j=i+l-1;
                B[i][j]=INT_MAX;
                for(int k=i;k<=j-1;k++){
                    q=B[i][k]+ B[k+1][j]+ (arr[i].r*arr[k].c*arr[j].c);
                    if(q<B[i][j]){
                        B[i][j]=q;
                        s[i][j]=k;
                    }
                }
            }
        }
        aux=1;
        printf("Case %d: ",cont);cont++;
        Imprimir(aux,n); printf("\n");

     }

    return 0;
}