1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 int max(int a,int b) 8 { 9 return a>b?a:b;10 }11 12 int maxDestroy(int* nums, int numsSize) {13 int arr[numsSize+2];14 int i,j,k;15 for(i = 1;i < numsSize+1;i ++)16 {17 arr[i] = nums[i-1];18 }19 arr[0] = arr[numsSize+1]=1;20 21 int dp[numsSize+2][numsSize+2];22 for(i = 0;i < numsSize+2;i ++)23 for(j = 0;j < numsSize+2;j ++)24 dp[i][j] = 0;25 int n = numsSize+2;26 27 for(k = 2;k < n;k ++)28 {29 int left,right;30 for(left = 0;left
           
            < right;i ++)34 {35 dp[left][right] = max(dp[left][right],36 arr[left]*arr[i]*arr[right]+dp[left][i]+dp[i][right]);37 }38 }39 }40 return dp[0][n-1];41 }42 int main()43 {44 int building_num;45 while(~scanf("%d",&building_num))46 {47 int i;48 int nums[building_num];49 for(i = 0;i < building_num;i ++)50 {51 scanf("%d",&nums[i]);52 }53 int result = maxDestroy( nums, building_num);54 printf("%d\n",result);55 }56 return 0;57 }