HDU You Are the One (dp)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int Ni = 105;
 6 const int inf = 1<<27;
 7 int n,num[Ni],sum[Ni],d[Ni][Ni];
 8 inline int min(int a,int b) {return a<b? a:b;}
 9 int dp(int i,int j)
10 {
11     int ans=inf;
12     if(d[i][j]!=inf) return d[i][j];
13     if(i==j) return d[i][j]=0;
14     d[i+1][j]=dp(i+1,j);
15     ans=min(ans,d[i+1][j]+sum[j]-sum[i]);
16     ans=min(ans,d[i+1][j]+num[i]*(j-i));
17     for(int k=i+1;k<j;k++)
18     {
19         d[i+1][k]=dp(i+1,k);
20         d[k+1][j]=dp(k+1,j);
21         ans=min(ans,d[i+1][k]+d[k+1][j]+num[i]*(k-i)
22                 +(sum[j]-sum[k])*(k-i+1));
23     }
24     return d[i][j]=ans;
25 }
26 int main()
27 {
28     int t,i,j,cs=1;sum[0]=0;
29     scanf("%d", &t);
30     while(t--)
31     {
32         scanf("%d",&n);
33         for (i=1;i<=n;i++)
34         {
35             scanf("%d",num+i);
36             sum[i]=sum[i-1]+num[i];
37         }
38         for (i=1;i<=n;i++)
39             for (j=1;j<=n;j++) d[i][j]=inf;
40         printf("Case #%d: %d\n",cs++,dp(1,n));
41     }
42     return 0;
43 }