/*
 * Compute the prioirty of matrix multiplications
 * (in a multiplication chain) that minimizes
 * the number of operations needed in total.
 * Using dynamic programming (memoize)
 */

#include <iostream>
#include <vector>
#include <list>

using namespace std;
using vint = vector<int>;
using vstr = vector<string>;
using vvchar = vector<vector<char>>;

/*
 * Binary tree node. Used to represent multiplication priorities
 */
struct BNode{
    int v;
    BNode* l;
    BNode* r;
    BNode(int val): v(val), l(nullptr), r(nullptr){}
    bool isLeaf(){
        return l == nullptr && r == nullptr;
    }
};

/*
 * Wrapper struct, contains total number of multiplications and the multiplication priorities
 */
struct Result{
    long multCount;
    BNode* paren;

    Result(){}
    Result(long mc, BNode* p){
        multCount = mc;
        paren = p;
    }
};
using vvres = vector<vector<Result*>>;

/*
 * Recursive helper function to 'parenthesize(string &s, BNode* n)'
 */
string parenthesizeUtil(string &s, BNode* n){
    // base case + recurr
    string left;
    string right;
    if(n->l == nullptr){
        left = s[n->v];
    }else{
        left = parenthesizeUtil(s, n->l);
    }
    if(n->r == nullptr){
        right = s[n->v+1];
    }else{
        right = parenthesizeUtil(s, n->r);
    }
    if(left.size()>1)
        left = '(' + left + ')';
    if(right.size()>1)
        right = '(' + right + ')';
    return left+right;
}

/*
 * Utility function to build parenthesized/prioritized multiplication string
 */
string parenthesize(string &s, BNode* n){
    if(n==nullptr) return s;
    return parenthesizeUtil(s, n);
}

/*
 * Recursive memoizing helper function to 'findMinimumParentheses(vint &v)'
 * Maintains a table, updates table and fetches when query is present
 */
Result findMinimumParenthesesUtil(vint &v, int l, int r, vvres &table){
    // memoize
    if(table[l][r]!= nullptr) return *(table[l][r]);

    // base case
    if(r-l<2){
        auto* res = new Result(0, nullptr);
        table[l][r] = res;
        return *res;
    }
    if(r-l==2){
        auto* res = new Result(v[l]*v[l+1]*v[l+2], new BNode(l));
        table[l][r] = res;
        return *res;
    }

    // recurr
    auto* resBest = new Result(LONG_MAX, nullptr);
    for (int i=l+1; i<=r-1; ++i) {
        Result resL = findMinimumParenthesesUtil(v, l, i, table);
        Result resR = findMinimumParenthesesUtil(v, i, r, table);
        if(resL.multCount + resR.multCount + v[l]*v[i]*v[r] < resBest->multCount){
            resBest->multCount = resL.multCount + resR.multCount + v[l]*v[i]*v[r];
            resBest->paren =  new BNode(i-1);
            resBest->paren->l = resL.paren; resBest->paren->r = resR.paren;
        }
    }

    // save
    table[l][r] = resBest;
    return *resBest;
}

/*
 * Given a vector<int> of matrix dimensions,
 * computes the optimal way to performing chain multiplication
 * Returns the 'result' containing total number of multiplications
 * and the 'way' to multiply represented as a binary tree
 */
Result findMinimumParentheses(vint &v){
    vvres table(v.size(), vector<Result*>(v.size(), nullptr));
    return findMinimumParenthesesUtil(v, 0, v.size()-1, table);
}

/*
 * Driver function
 */
int main(){
//    string s = "ABC";
//    vint v({10,30,5,60});

    string s = "AB"; // two matrices
    vint v({10, 20, 30}); // A is (10,20), B is (20,30)

    Result res = findMinimumParentheses(v);
    cout << res.multCount << endl;

    string p = parenthesize(s,res.paren);
    cout << p;

    return 0;
}