有一个栈，你可以把这个栈中的数吐到另一个栈中去，然后每次可以从两个栈中选择一个数出栈，使∑num[i]*(i-1)最小，num[i]代表第i个出栈的数。

　　比赛的时候一直没想法，看了解题报告才恍然大悟。。对于每个区间，枚举第一个人是第几个出栈的，假设区间是[L,R],第一个人是i个出栈的，那么这个栈就被分成了三部分，[L,L],[L+1,L+i],[L+i+1,R]，对后面两个区间看作子问题继续DP，注意对后面一个区间要加上(sum[R]-sum[L+i-1])*i，sum[i]表示前缀和。

　　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define INF 0x3f3f3f3f 5 int cas,n,xx[105],sum[105],d[105][105]; 6 int dp(int l,int r){ 7     if(d[l][r]!=INF)return d[l][r]; 8     if(l>=r)return 0; 9     for(int i=1;i<=r-l+1;i++){10         int tmp=dp(l+1,l+i-1)+dp(l+i,r)+xx[l]*(i-1)+(sum[r]-sum[l+i-1])*i;11         d[l][r]=std::min(d[l][r],tmp);12     }13     return d[l][r];14 }15 int main(){16     scanf("%d",&cas);17     for(int ca=1;ca<=cas;ca++){18         scanf("%d",&n);19         for(int i=1;i<=n;i++){20             scanf("%d",&xx[i]);21             sum[i]=sum[i-1]+xx[i];22         }23         memset(d,0x3f,sizeof d);24         printf("Case #%d: %d\n",ca,dp(1,n));25     }26     return 0;27 }