[kuangbin带你飞]专题二十二 区间DP-E-POJ - 1651

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
LL dp[106][106];
LL a[106];
const int INF = 0x3f3f3f3f;
int main(){
   int n;
   while(~scanf("%d",&n)){
    memset(dp,0,sizeof(dp));
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for (int len=3;len<=n;len++){
        for (int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=INF;
            for (int k=i+1;k+1<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
            }
        }
    }
    printf("%lld\n",dp[1][n]);
   }
   return 0;
}