HDU 4283---You Are the One（區間DP），hdu4283---you

HDU 4283---You Are the One（區間DP），hdu4283---you

題目鏈接

http://acm.split.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)   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   Source 2012 ACM/ICPC Asia Regional Tianjin Online   Recommend liuyiding   |   We have carefully selected several similar problems for you:  4267 4268 4269 4270 4271    題意：有n個人，輸入n個基值（憤怒值）v[]，表示每個人的憤怒值，現在他們依次上台表演，如果i是第k個上台，那麼他的憤怒值為（k-1）*v[i]  現在有一個棧，可以讓一些人進棧，讓後面的人先上台表演，這樣可以改變部分順序，求所有人最小的憤怒值和；   思路：區間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[]表示前綴和;   代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int inf=0x7fffffff;
int v[105];
int dp[105][105];
int sum[105];

int main()
{
    int T,n,Case=1;
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
            sum[i]=sum[i-1]+v[i];
        }
        for(int i=1;i<=n;i++)
            dp[i][i]=0;
        for(int len=1;len<n;len++)
        {
            for(int i=1;i+len<=n;i++)
            {   ///特判i在i~i+len的區間中是第一個和最後一個時的情況；
                dp[i][i+len]=min(sum[i+len]-sum[i]+dp[i+1][i+len],dp[i+1][i+len]+v[i]*len);
                for(int k=2;k<=len;k++)
                dp[i][i+len]=min(dp[i][i+len],v[i]*(k-1)+dp[i+1][i+k-1]+(sum[i+len]-sum[i+k-1])*k+dp[i+k][i+len]);
            }
        }
        printf("Case #%d: %d\n",Case++,dp[1][n]);
    }
}