Solution UVA: 348 - Optimal Array Multiplication Sequence

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss348 - Optimal Array Multiplication Sequence	Accepted	C++11	0.200	0.000	2357

Suggest:
- I only view tutorial in youtube Matrix Chain Multiplication and then code it by Top-down DP

#include<bits/stdc++.h>

#define X first

#define Y second

#define int long long

using namespace std;

const int N= 1000111;

int L[N], R[N];

unordered_map<int, pair<int, string>> F[11];

pair<int, string> f(int i, int j){

    if (F[i].count(j)) return F[i][j];

    if (i == j) return {0, "A"+to_string(i)};

    if (i+1 == j) return {L[i]*R[i]*R[j], "(A"+to_string(i)+" x A"+to_string(j)+")"};

   

    int x = 1e18;

    string y;

   

    for(int k=i; k<j; k++){

       

        auto p1 = f(i, k);

        int x1 = p1.X;

        string y1 = p1.Y;

       

        auto p2 = f(k+1, j);

        int x2 = p2.X;

        string y2 = p2.Y;

       

        int val = L[i] * R[k] * R[j];

           

        if (x > x1 + x2 + val){

           

            x = x1 + x2 + val;

            y = "("+y1+" x "+y2+")";

        }  

    }

    return F[i][j] = {x,y};

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int n, cnt= 0;

    while(cin >> n && n){

        for(int i=1; i<=n; i++)

            cin >> L[i] >> R[i];

       

        for(int i=1; i<=10; i++) F[i].clear();

       

        cout<<"Case "<<++cnt<<": "<<f(1, n).Y<<"\n";    

    }

   

}