SMMR-099: MTrap

#include <bits/stdc++.h>
using namespace std;
const long long INF=2e18;
long long dp[410][410];
int main(){
    int n;
    scanf("%d",&n);
    vector <long long> v;
    for(int i=1;i<=n;i++){
        long long x,y;
        scanf("%lld %lld",&x,&y);
        if(i==1) v.push_back(x);
        v.push_back(y);
    }

    for(int i=v.size()-1;i>=1;i--){
            for(int j=1;j<=v.size()-1;j++){
                if(i==j){
                    dp[i][j]=0;
                    continue;
                }
                dp[i][j]=INF;
                for(int k=i;k<j;k++){
                    long long x;
                    x = dp[i][k] + dp[k+1][j] + v[i-1]*v[k]*v[j];
                    dp[i][j] = min(dp[i][j] , x);
                }
            }
        }
    printf("%lld\n",dp[1][v.size()-1]);
    return 0;
}