Day8.cpp

//Brackets in Matrix Chain Multiplication 
// { Driver Code Starts
// Initial Template for C++

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

 // } Driver Code Ends
// User function Template for C++

class Solution{
public:
    void genAns(int st, int end,vector< string >& ans, vector< vector<int> >& divn){
    if(end-st == 0)
        return ;
    genAns(st,divn[st][end],ans,divn) ;
    genAns(divn[st][end]+1,end,ans,divn) ;
    ans[st] = "(" + ans[st] ;
    ans[end] = ans[end] + ")" ;
}

string matrixChainOrder(int p[], int n){
    vector< vector<int> > dp(n-1, vector<int>(n-1)), divn(n-1, vector<int>(n-1,-1)) ;
    for(int size=2 ; size<=n-1 ; size++){
        for(int st=0 ; st+size-1 <= n-2 ; st++){
            dp[st][st+size-1] = INT_MAX ;
            for(int k=st ; k<st+size-1 ; k++){
                if(dp[st][st+size-1] > p[st]*p[k+1]*p[st+size] + dp[st][k] + dp[k+1][st+size-1]){
                    dp[st][st+size-1] = p[st]*p[k+1]*p[st+size] + dp[st][k] + dp[k+1][st+size-1] ;
                    divn[st][st+size-1] = k ;
                } 
            }
        }
    }
    vector< string > ans(n-1) ;
    for(int i=0 ; i<n-1 ; i++){
        ans[i] = 'A'+i ;
    }
    
    genAns(0,n-2,ans,divn) ;
    string fans ;
    for(int i=0 ; i<n-1 ; i++)
        fans += ans[i] ;
    return fans ;
}
};

// { Driver Code Starts.

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int p[n];
        for(int i = 0;i < n;i++)
            cin>>p[i];
        
        Solution ob;
        cout<<ob.matrixChainOrder(p, n)<<"\n";
    }
    return 0;
}  // } Driver Code Ends