You Are the One DP

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 #define inf 10000000000LL
 6 long long dp[200][200];
 7 
 8 int main()
 9 {
10     freopen("in.txt","r",stdin);
11     long long t,n,i,j,a[200],sum[200],k,cas=1;
12     scanf("%I64d",&t);
13     while(t--)
14     {
15         sum[0]=0;
16         scanf("%I64d",&n);
17         for(i=1; i<=n; i++)
18             scanf("%I64d",&a[i]),sum[i]=sum[i-1]+a[i];
19         for(i=0; i<=n; i++)
20             for(j=i; j<=n; j++)if(i!=j)dp[i][j]=inf;
21                 else dp[i][j]=0;
22          int l=1;
23          while(l<n)
24          {
25              for(i=1;i+l<=n;i++)
26              {
27                  dp[i][i+l]=min(dp[i][i+l],dp[i+1][i+l]+sum[i+l]-sum[i]);
28                  dp[i][i+l]=min(dp[i][i+l],dp[i+1][i+l]+a[i]*l);
29                  for(k=1;k<l;k++)
30                  dp[i][i+l]=min(dp[i][i+l],dp[i+1][i+k]+dp[i+k+1][i+l]+a[i]*k+(k+1)*(sum[i+l]-sum[i+k]));
31              }
32              l++;
33          }
34          cout<<"Case #"<<cas++<<": ";
35          cout<<dp[1][n]<<endl;
36     }
37 }