D - You Are the One
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)
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
设dp数组
dp[s][e]
表示从等待上的人中以第
s
和第 e 个人为首、尾，取出这个闭区间里的人，让他们上一个“虚拟的”舞台所需要的最小代价。这样，对一般情况进行考虑，可以得到如下状态转移方程：
dp[s][e]=min{dp[s+1][k]+dp[k+1][e]+(k−s+1)∗(sum[e]−sum[k])+(k−s)∗sample[s]}其中,k∈[s,e]sum[]表示屌丝值的前缀和sample[]表示s所处位置上的人之屌丝值
理解这个方程的含义，即可描述题目的解析过程：
方程假定对每个枚举的区间 [s,e] 都取出第一位，即位置为 s 的那一位男生，尝试着将他在区间中的每个位置都放一下（具体为位置 k），计算这样操作之后的最小代价。这样，我们可以容易地理解方程中
dp[s+1][k]
的含义，即 s 位置的男生移动到 k 位置后，他前面的
k−1
个人对应的最小代价；而由于第一位的男生移动到了位置 k，他对应的代价相应地由
0
变为 k−s 再乘上他自身的屌丝值。
方程中的
dp[k+1][e]+(k−s+1)∗(sum[e]−sum[k])
没有那么直观，但含义其实也可以较易地理解，即第一位的男生移动到位置 k 后，晚于他上场的人对应的总代价。
具体是说，由于
dp[s][e]
表示的是“所给区间中的男生单独取出，假定他们是最先上场”的情况下的最小代价，将他们与之前的区间 [s,k] 的若干人组成一个整体时，相当于 [k+1,e] 区间中的这些人集体推迟了若干位上场。于是需要为他们增加这额外的代价，于是就有了区间单独考虑上场的代价
dp[k+1][e]
加上他们推迟若干位的额外代价
(k−s+1)∗(sum[e]−sum[k])
。
这题题目中描述了一个栈，但直接从套用STL的角度出发来思考是很难的。实际上描述的含义是告诉我们，可以不用考虑具体出入栈过程，而是直接考虑出入栈的效果，并且
(k−1)×D
的个人代价都蕴含在了递推式中。这是题目的难点。
另：对于dp数组的清零确保了dp的下标 s 大于 e 时依然可以不加格外判断地得到正确结果。
又：命题人英文水平真差
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int INF =
0x7fffffff;
int sample[
104], dp[
104][
104], sum[
104];
int main(){
#ifdef TEST
freopen(
"test.txt",
"r", stdin);
#endif
int T, n;
cin >> T;
for(
int t =
1; t <= T; t++){
memset(dp,
0,
sizeof(dp));
memset(sum,
0,
sizeof(sum));
cin >> n;
for(
int i =
1; i <= n; i++){
cin >> sample[i];
sum[i] = sum[i-
1] + sample[i];
}
for(
int len =
1; len <= n-
1; len++){
for(
int s =
1, e =
1+len; e <= n; s++, e++){
dp[s][e] = INF;
for(
int k = s; k <= e; k++){
dp[s][e] = min(dp[s][e], dp[s+
1][k] + dp[k+
1][e] + (k-s+
1)*(sum[e]-sum[k]) + (k-s)*sample[s] );
}
}
}
printf(
"Case #%d: %d\n", t, dp[
1][n]);
}
return 0;
}
