HDU4283 You Are the One（區間dp）

You Are the One

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2714Accepted Submission(s): 1247

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)

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個人按1,2,3...n的順序排好，每個人都有一個unhappy值；如果第i個人第k個上台，那麼他的unhappy值為（k-1)*unhappy[i]。他們上台前需要經過一個小黑屋（就相當於是堆棧。。。） 分析：不能用堆棧來寫，用了就錯了，，，其實是個區間dp，比較難一點；dp[i][j]表示區間[i,j]最小不開心總值。那麼對於dp[i][j]的第i個人，就有可能第1個上場，也可以第j-i+1個上場。考慮第K個上場
即在i+1之後的K-1個人是率先上場的，那麼就出現了一個子問題 dp[i+1][i+1+k-1-1]表示在第i個人之前上場的
對於第i個人，由於是第k個上場的，那麼憤怒值便是a[i]*(k-1)
其余的人是排在第k+1個之後出場的，也就是一個子問題dp[i+k][j]，對於這個區間的人，由於排在第k+1個之後，所以整體憤怒值要加上(sum[j]-sum[i+k-1])*k。

<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include<map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 1<<27;
const int MOD = 1000000007;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define MAXN 100010

int a[105],sum[105],dp[105][105];

int main()
{
    int T,n;
    scanf("%d",&T);
    for(int cas=1; cas<=T; cas++)
    {
        scanf("%d",&n);
        sum[0] = 0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        CL(dp, 0);
        for(int i=1; i<=n; i++)
            for(int j=i+1; j<=n; j++)
                dp[i][j] = INF;
        for(int l=1; l<=n-1; l++)
        {
            for(int i=1; i<=n-l; i++)
            {
                int j = i+l;
                for(int k=i; k<=j; k++)
                    dp[i][j] = min(dp[i][j], dp[i+1][k]+dp[k+1][j]+a[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));
            }
        }
        printf("Case #%d: %d\n",cas,dp[1][n]);
    }
    return 0;
}
</algorithm></cmath></vector></set></map></queue></stack></cstring></cstdio></iostream></span>