http://acm.hdu.edu.cn/showproblem.php?pid=4283
Problem Description
The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the show itself. The show is hold in the Small hall, so it attract a lot of boys and girls. Now there are n boys enrolling in. At the beginning, the n boys stand in a row and go to the stage one by one. However, the director suddenly knows that very boy has a value of diaosi D, if the boy is k-th one go to the stage, the unhappiness of him will be (k-1)*D, because he has to wait for (k-1) people. Luckily, there is a dark room in the Small hall, so the director can put the boy into the dark room temporarily and let the boys behind his go to stage before him. For the dark room is very narrow, the boy who first get into dark room has to leave last. The director wants to change the order of boys by the dark room, so the summary of unhappiness will be least. Can you help him?
Input
The first line contains a single integer T, the number of test cases. For each case, the first line is n (0 < n <= 100)
The next n line are n integer D1-Dn means the value of diaosi of boys (0 <= Di <= 100)
The next n line are n integer D1-Dn means the value of diaosi of boys (0 <= Di <= 100)
Output
For each test case, output the least summary of unhappiness .
Sample Input
2 5 1 2 3 4 5 5 5 4 3 2 2
Sample Output
Case #1: 20 Case #2: 24
有n个男孩，现在要一个一个的登台，每个男孩都有一个diaosi值，如果他是第k个登台的，他的最终的diaosi值就等于他的diaosi值*（k-1),他前边等待了K-1个人，现在要确定一个登台顺序 ，使得所有男孩的diaosi值最小
有一群屌丝，每个屌丝有个屌丝值，如果他第K个上场，屌丝值就为a[i]*(k-1),同过一个小黑屋来调整，是的最后总屌丝值最小。
（注意：顺序必须在原来顺序的基础上改，要按原来的顺序选择是进小黑屋还是上场，不能简单的从大到小排序，再计算）。
题解：
区间dp,枚举区间长度，在这段区间中，dp[i][j]表示i 在[i,j]中第k个上场的最优解。
dp[i][j] = min ( dp[i][j], dp[i + 1][k + i - 1] + dp[i + k][j] + k * ( sum[j] - sum[i + k - 1] ) + a[i] * ( k - 1 ) )
3、思路分析
设状态dp[i][j]表示i-j区间内i是第k个登台的
dp[s][e]=min(dp[s][e],dp[s+1][e]+a[s]*(e-s));//s是最后一个选出来的
dp[s][e]=min(dp[s][e],dp[s+1][e]+Delay(s,e));//第一个被选出来
for(int k=s+1;k<=e;k++)
{
dp[s][e]=min(dp[s][e],dp[s+1][k]+dp[k+1][e]+a[s]*(k-s)+Delay(k,e)*(k-s+1));
//最后是k-s+1,k后边的人还要等k
}
dp(l,r)dp(l,r)表示第ll到第rr个人作为前r−l+1r−l+1个人上场的最小不高兴值，答案即为dp(1,n)dp(1,n)
枚举第ll个人的上场次序，如果第ll个人在这r−l+1r−l+1个人中是第i(1≤i≤r−l+1)i(1≤i≤r−l+1)个上场的，由于是通过一个栈调整顺序，且进栈是按编号从小到大的，故第ll个人后面的i−1i−1个人必然在第ll个人上场前已经上场了，那么由第ll个人产生的不高兴值即为(i−1)∗Dl(i−1)∗Dl，第l+1l+1到第l+i−1l+i−1这i−1i−1个人产生的不高兴值为dp(l+1,l+i−1)dp(l+1,l+i−1)，剩下的人产生的不高兴值为dp(l+i,r)+i∗∑j=l+irDjdp(l+i,r)+i∗∑j=l+irDj，加上第二部分的值是因为在这些人表演之前又多了ii个人表演
int T,n,a[maxn],sum[maxn],dp[maxn][maxn];
int dfs(int l,int r)
{
if(l>=r)return 0;
if(dp[l][r]!=-1)return dp[l][r];
dp[l][r]=INF;
for(int i=l;i<=r;i++)
dp[l][r]=min(dp[l][r],(i-l)*a[l]+dfs(l+1,i)+dfs(i+1,r)+(i-l+1)*(sum[r]-sum[i]));
return dp[l][r];
}
int main()
{
int res=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
memset(dp,-1,sizeof(dp));
printf("Case #%d: %d\n",res++,dfs(1,n));
}
return 0;
}
思路：区间DP，定义dp[i][j]表示原序列中i到j的人的最小愤怒值的和，设i在区间i到j中第k个上场，那么i+1~i+k-1会先i上台，然后i上台，最后i+k~i+len上台，那么状态转移方程为： dp[i][j]=v[i]*(k-1)+dp[i+1][i+k-1]+(sum[i+len]-sum[i+k-1])*k+dp[i+k][i+len] sum[]表示前缀和;
將n個男嘉賓重新排序出場（使用一個棧進行維護），第k個出場的人會有a【i】*（k-1）的厭惡值。
先不管使用棧的情況，dp【i】【j】表示從i到j的人出場的最低厭惡值（1~i-1和j+1~n的順序不變）；
在計算dp【i】【j】時，枚舉k，i＜＝ｋ＜＝ｊ，k的意義是第i個人的出場次序（即標號為i的人第k個出場）。
這樣一來在【i，j】區間內，從i+1到k的人要在i之前出場，k+1到j的人要在i之後出場
即轉化成兩個子問題：dp【i+1】【k】和dp【k+1】【j】；
所以dp【i】【j】=min（a[i]*(k-1)+dp[i+1][k]-(sum[k]-sum[i])+dp[k+1][j]）
注：因為dp【i+1】【k】整體向前挪了一位所以要減去一倍的和（上式中用前綴和表示，詳見代碼）
最後dp【1】【n】即為答案
发现其实只要调整一下区间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)的额外花费。
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<n; l++) 28 for (int i=1; i+l<=n; i++) 29 { 30 int j = i + l; 31 LL Min = INF; 32 for (int k=i; k<=j; k++) 33 { 34 LL num = a[i]*(k-i) + (arr[j] - arr[k])*(k-i+1) + dp[i+1][k] + dp[k+1][j]; 35 Min = min (Min, num); 36 } 37 dp[i][j] = Min; 38 } 39 printf ("Case #%d: %I64d\n", t, dp[1][n]); 40 }
