/*
 * Dynamic version, with better output.
 * cost[i][j] will be the cost of multiplying A_i * A_{i+1} * ... * A_{j­1}
 * best[i][j] is the best choice of the point of the last multiplication
 */

#include <stdio.h>

/* the example from the readings */
#define n 6
int s[n+1] = { 4, 2, 3, 1, 2, 2, 3 };

int cost[n+1][n+1];
int best[n+1][n+1];


int main()
{
    int i, len;
    extern void output_order(int i, int j);

    for (i = 0; i < n; i++) {
        cost[i][i+1] = 0;
        best[i][i+1] = i;
    }
    for (len = 2; len <= n; len++) {
        for (i = 0; i + len <= n; i++) {
            int j = i + len;
            int k = i + 1;
            best[i][j] = k;
            cost[i][j] = cost[i][k] + cost[k][j] + s[i]*s[k]*s[j];
            for (k++; k < j; k++) {
                if (cost[i][k] + cost[k][j] + s[i]*s[k]*s[j] < cost[i][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j] + s[i]*s[k]*s[j];
                    best[i][j] = k;
                }
            }
        }
    }
    output_order(0, n);
    return 0;
}


void output_order(int i, int j)
{
    int k = best[i][j];
    if (i < k) {
        printf("(");
        output_order(i, k);
        printf(") * ");
    }
    printf("A%d", k);
    if (k + 1 < j) {
        printf(" * (");
        output_order(k + 1, j);
        printf(")");
    }
}