#include<fstream>
#include<iostream>
using namespace std;
const int  MAX_INT = 0x7fffffff;
void print(int s[][7], int i, int j)
{
    if (i == j) cout << "A"  << i;
    else {
        cout << "(";
         print(s, i, s[i][j]);
         print(s, s[i][j] + 1, j);
         cout << ")";
    }
}
int main()
{
    int p[7] = {30,35,15,5,10,20,25 };
    int m[8][8],s[7][7];
    int x,i,j,l,k,q;
    for (x=1; x <7; x++)
        m[x][x] = 0;
    for ( l = 2; l <= 6; l++)
    {
        for ( i = 1; i <= 7-l; i++)
        {
              j=i+l-1;
             m[i][j] = MAX_INT;
             int q;
        //     cout << m[i][j];
            for ( k = i; k <j; k++)
            {
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    print(s, 1, 6);
    system("pause");
    return 0;
}