My solution of UVA 348 : Optimal Array Multiplication Sequence

The same idea with SRM 534 -  CasketofStarEasy


Minmize the number of multipication operations of A1 x A2 .....Ai X Ai+1 .... An


Core idea: recursive function 
#mult(1,N) = min(i) { mult(1,i) + mult(i+1,n) + R(a)*C(i)*C(b) }


Why R(a)*C(i)*C(b) ?

==> (Aa x...x Ai) becomes a matrix of Row(A1) X Column(Ai)
  & (Ai+1 x...x Ab) becomes a matrix of Row(Ai+1) X Column(Ab)
so the # of multiplication of product these two Matrix is R(a)*C(i)*C(b)

--------
Notice : please check how to generate the equation string by dynamic programming.


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cfloat>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define ms(x, a) memset((x), (a), sizeof(x))
#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end()) 
#define forr(i,b) for(int i=0;i<b;i++)
#define forg(i,j,n) for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)
#define nl(c) c<<endl;
#define db(cout,c) tr(c,it){cout<<*it<<",";};nl(cout); 
#define db2(cout,c) tr(c,it2){db(cout,*it2);};nl(cout); 


#define NN 64
using namespace std;


long long mem[NN][NN];
string ss[NN][NN];
long long C[NN],R[NN];


//N items 0..N-1
//N-1 operator
long long rec(int a, int b)
{
    long long &res=mem[a][b];
    long long min=(1LL<<63)-1;
    if(res==-1)
    {
        res=0;
        int ri=0;
        ss[a][b]="";
        if(b<=a){
            stringstream s;
            s<<"A"<<a+1;
            ss[a][b]=s.str();
            return res;
        }
        for(int i=a;i<b;i++)
        {
            long long r = R[a]*C[i]*C[b]+rec(a,i)+rec(i+1,b);
            if(r<min)
            {
                min=r;
                ri=i;
            }
        }
        ss[a][b]="("+ss[a][ri]+" x "+ss[ri+1][b]+")";
        res=min;
    }
    return res;
}


int main(int argc, char *argv[])
{
    int N,T=0;
    while(cin>>N)
    {
        if(N==0)break;
        T++;
        cout<<"Case "<<T<<": ";
        forr(i,N)
        {
            cin>>R[i]>>C[i];
        }
        forr(i,N)
        forr(j,N)
        mem[i][j]=-1LL;
        rec(0,N-1);
        
       cout<<ss[0][N-1]<<endl;
    }
    return 0;
}