题目链接：

　　

题目描述：

　　给出n个数，每个数要先进栈然后出栈，第i个出栈的数a，花费的价值是(i-1)*a.问所有的数出栈花费的最小价值是多少？

解题思路：

　　额······，区间DP专题里面的题目。区间DP不是唯一的解法，应该也是可行解咯。难点就是在于如何模拟栈的进出，胡乱YY，写了一发也是wa。然后搜了一下题解，发现其实只要调整一下区间Dp时候的策略就好辣。由于要满足出栈的条件，所以只能进行微调。dp[x][y] 表示 区间 [x, y] 上所有的数出栈后的最小花费。那么对于区间 [x, y] 中的数字 a[x]，有可能第1个出栈，也有可能最后一个出栈，如果第i个出栈的话前i-1个数字要按照顺序出栈，然后a[x]出栈，[i+1,y]出栈。对于a[x]要加上a[x]*i的花费，对于[i+1, y]要加上sum(i+1, y) * (i-x+2)的额外花费。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 typedef __int64 LL; 8 const int INF = 0xfffffff; 9 const int maxn = 110;10 LL dp[maxn][maxn], a[maxn], arr[maxn];11 12 int main ()13 {14     int T, n;15     scanf ("%d", &T);16     for (int t=1; t<=T; t++)17     {18         scanf ("%d", &n);19         a[0] = arr[0] = 0;20         for (int i=1; i<=n; i++)21         {22             scanf ("%I64d", &a[i]);23             arr[i] = arr[i-1] + a[i];24         }25 26         memset (dp, 0, sizeof(dp));27         for (int l=1; l