1 //Accepted    200 KB    0 ms 2 //dp区间 3 //dp[i][j]=min(dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]) i<k<j 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 const int imax_n = 105; 9 const int Pinf = 100000000;10 int dp[imax_n][imax_n];11 int a[imax_n];12 int n;13 int min(int a,int b)14 {15     return a<b?a:b;16 }17 void Dp()18 {19     for (int i=1;i<=n-2;i++)20     dp[i][i+2]=a[i]*a[i+1]*a[i+2];21     for (int l=4;l<=n;l++)22     {23         for (int i=1;i<=n;i++)24         {25             int j=i+l-1;26             if (j>n) break;27             dp[i][j]=Pinf;28             for (int k=i+1;k<j;k++)29             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);30             //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);31         }32     }33     printf("%d\n",dp[1][n]);34 }35 int main()36 {37     while (scanf("%d",&n)!=EOF)38     {39         for (int i=1;i<=n;i++)40         scanf("%d",&a[i]);41         Dp();42     }43     return 0;44 }