1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 11111111 6 using namespace std; 7 const int maxn = 105; 8 int a[maxn],dp[maxn][maxn]; 9 int main()10 {11     //freopen("in.txt","r",stdin);12     int n;13     while(cin>>n)14     {15         for(int i = 1;i<=n;++i)16             scanf("%d",&a[i]);17         for(int i = 0;i<=n;++i)18             for(int j = 0;j<=n;++j)19                 dp[i][j] = INF;20         for(int i = 2;i<n;++i)21             dp[i][i] = a[i-1]*a[i]*a[i+1];22         for(int r = 2;r<=n-2;++r)23             for(int i = 2;i<=n-r+1;++i)24             {25                 int j = i+r-1;26                 for(int k = i;k<=j;++k)27                 {28                     if(k==i)dp[i][j] = min(dp[i][j],dp[i+1][j]+a[i-1]*a[i]*a[j+1]);29                     else if(k==j)dp[i][j] = min(dp[i][j],dp[i][j-1]+a[i-1]*a[j]*a[j+1]);30                     else dp[i][j] = min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[i-1]*a[k]*a[j+1]);31                 }32             }33         printf("%d\n",dp[2][n-1]);34     }35     return 0;36 }