HDU4283 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

题意：
   诸如You Are One的电视节目非常受欢迎。为了满足仍然单身的男孩的需要，TJUT自行举办了表演。表演在小型大厅举行，因此吸引了很多男孩
和女孩。现在有n个男孩报名参加。起初，n个男孩排成一列，一个个地进入舞台。但是，导演突然知道，这个男孩的价值是diaosi D，如果男孩第k
个进入舞台，他的不幸将是（k-1）* D，因为他必须等待（ k-1）个人。幸运的是，在小礼堂中有一间暗室，因此导演可以将男孩暂时放到暗室中，
并让身后的男孩在他之前登上舞台。由于暗室非常狭窄，因此首先进入暗室的男孩必须最后离开。
导演想在黑暗的房间里改变男孩的顺序，所以对不幸的总结最少。你能帮他吗？

输入：
   第一行包含一个整数T，即测试用例的数量。对于每种情况，第一行都是n（0 <n <= 100）
   接下来的n行是n个整数D1-Dn表示男孩的diaosi值（0 <= Di <= 100）

   输出： 

         对于每个测试用例，请输出最少的不满意摘要。

   知识点： 区间DP    暗室里的顺序相当于一个栈

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int inf = 10000000;
 6 int n,val[105],sum[105],dp[105][105]; 
 7 int main()
 8 {
 9 
10     int t,i,j,k,l,cas = 1;
11     scanf("%d",&t);
12     while(t--)
13     {
14         scanf("%d",&n);
15         memset(sum,0,sizeof(sum));
16         for(i = 1; i<=n; i++)
17         {
18             scanf("%d",&val[i]);
19             sum[i] = sum[i-1]+val[i];
20         }
21         memset(dp,0,sizeof(dp));
22         for(i = 1; i<=n; i++)
23         {
24             for(j = i+1; j<=n; j++)
25                 dp[i][j] = inf;
26         }
27         for(l = 1; l<n; l++)
28         {
29             for(i = 1; i<=n-l; i++)
30             {
31                 j = i+l;
32                 for(k = 1; k<=j-i+1; k++)
33                     dp[i][j] = min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+k*(sum[j]-sum[i+k-1])+val[i]*(k-1));
34             }
35         }
36         printf("Case #%d: %d\n",cas++,dp[1][n]);
37     }
38     return 0;
39 
40 }

HDU4283 You Are the One

原文：https://www.cnblogs.com/linda-/p/13335566.html