MCM

#include<bits/stdc++.h>
using namespace std;

#define     read            freopen("input.txt","r",stdin)
#define     write           freopen("output.txt","w",stdout)

const int MAXN = 101;

int dp[MAXN][MAXN];

int call(int arr[], int i, int j)
{
    if(i == j) return 0;
    if(dp[i][j] != 0) return dp[i][j];
    dp[i][j] = INT_MAX;
    for(int k=i; k<j; k++)
    {
        int x = call(arr, i, k) + call(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
        if(x < dp[i][j])
        {
            dp[i][j] = x;
            dp[j][i] = k;
        }
    }
    return dp[i][j];
}

void printParenthesis(int i, int j)
{
    if(i==j)
        cout << "A" << i;
    else
    {
        cout << "(";
        int k = dp[j][i];
        printParenthesis(i, k);
        printParenthesis(k + 1, j);
        cout << ")";
    }
}

int main()
{
    read;
    write;
    int n;
    memset(dp, 0,sizeof(dp));
    cin >> n;
    int arr[n];
    for(int i=1; i<=n; ++i)
    {
        cin >> arr[i-1] >> arr[i];
    }
    cout << call(arr,1,n) << endl;
    printParenthesis(1, n);
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            printf("%7d", dp[i][j]);
        cout << endl;
    }
}


/*
input from: Cormen - page 376, 377
6
30 35
35 15
15 5
5 10
10 20
20 25
*/