# 目次

• 目次
• 解答
• 解答

# 解答

Naive recursive solution.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define INTMAX (1 << 21)

#define MAX 100


Int mcm(Int p[], Int left, Int right) {
    
    if (left == right) return 0;
    
    Int min_ = INTMAX;
    loop(sep,left,right) {
        Int cost = mcm(p, left, sep) + mcm(p, sep+1, right);
        cost += p[left - 1] * p[sep] * p[right];
        if (cost < min_) min_ = cost;
    }
    
    return min_;
}


int main(void) {
    Int n;
    cin >> n;
    Int p_len = n + 1;
    Int p[p_len];
    cin >> p[0] >> p[1];
    loop(i, 2, p_len) {
        cin >> p[i] >> p[i];
    }
    cout << mcm(p, 1, n) << endl;
    return 0;
}

# 解答

Bottom up dynamic programming. O(n^3)

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define INTMAX (1 << 21)

#define MAX 100


Int mcm(Int p[], Int n) {
    Int mincosts[n][n];
    loop(i,1,n) mincosts[i][i] = 0;
    
    loop(chain,2,n) {
        loop(l,1,n-chain+1) {
            Int r = l + chain - 1;
            mincosts[l][r] = INTMAX;
            loop(k,l,r) {
                Int cost = mincosts[l][k] + mincosts[k+1][r];
                cost += p[l-1] * p[k] * p[r];
                if (cost < mincosts[l][r]) mincosts[l][r] = cost;
            }
        }
    }
    
    return mincosts[1][n-1];
}


int main(void) {
    Int n;
    cin >> n;
    Int p_len = n + 1;
    Int p[p_len];
    cin >> p[0] >> p[1];
    loop(i, 2, p_len) {
        cin >> p[i] >> p[i];
    }
    cout << mcm(p, p_len) << endl;
    return 0;
}