题意：每个人有一个DI值，现在有一个小黑屋，这些人的顺序可以利用这个小黑屋调整，调整方式是入栈出栈方式，也就是说，这里的方案是有卡特兰数个方式。

调整后使得 d1*0 + d2*1 + d3*2 + d4*3 ...... 最小。

 

分析：这个题目竟然会是区间DP。

考虑区间 [ L, R ] ，那么L，可以从任意位置出栈，枚举出栈位置，可以划分为两个部分，也就是说两个子问题，但是如何利用这两个子问题得到 d[L,R]，

d[L,R] = 前一部分 + D[L]*(i-L) + 后一部分 + 后一部分进位。

其中，后一部分的进位是一个前缀和*进多少位。

#include 
      
       using namespace std;const int maxn = 105;const int inf = 0x3f3f3f3f;int a[maxn];int d[maxn][maxn];int su[maxn];int dp(int L,int R) {    if(L>=R) return 0;    if(d[L][R]!=-1) return d[L][R];    d[L][R] = inf;    for(int i=L;i<=R;i++) {        d[L][R] = min(d[L][R], dp(L+1, i)+(i-L)*a[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L));    }    return d[L][R];}int main(){    //freopen("in.txt","r",stdin);    int t;    scanf("%d",&t);    int kase = 1;    while(t--) {        int n;        scanf("%d",&n);        memset(d,-1,sizeof(d));        memset(su,0,sizeof(su));        for(int i=1;i<=n;i++) {            scanf("%d",&a[i]);            su[i] = su[i-1] + a[i];     //前缀和        }        printf("Case #%d: %d\n",kase++,dp(1,n));    }    return 0;}