Contest1339/C.cpp

#include<bits/stdc++.h>
 
using namespace std;
const int MAXN = 100;
int m[MAXN][MAXN];
 
void dp_chains(vector<int> p) {
    int n = p.size() - 1;
    for (int i = 1; i <= n; i++)m[i][i] = 0;
    for (int l = 2; l <= n; l++)
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = INT_MAX >> 2;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                m[i][j] = min(q, m[i][j]);
            }
        }
 
}
 
int main() {
    int n;
    cin >> n;
    vector<int> p(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> p[i + 1];
    }
 
    //recursive_chains(p, 1, n);
    dp_chains(p);
 
    cout << m[1][n] << endl;
 
    return 0;
}