HDU-4283

2018-03-02

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4283

题目大意

有一群人排成一队，然后每人有一个屌丝值，有k个人在他前面，那他的怒气值就是k*屌丝值。
现在有一个小黑屋，小黑屋的规则类似栈，先进后出。进入小黑屋后，该人后面的可以比他提前入场。问最小的队伍总怒气值是多少。

思想

这是一个区间DP，我们在1……n这些人中取第i到第j个人，先不考虑头尾，只考虑中间这j-i+1个人。
记dp[i][j]为从i到j这个区间内的最小怒气值。

对于这j-i+1个人来说：
第i个人可以是第一个进场，也可以是第j-i+1个进场（最后一个），我们不妨设第i个人第k个进场（注意，这个k是相对于i……j来说的）。
我们将i……j分为三部分，第一块为比i提前入场的k-1个人；第二部分为i；第三部分为比i后入场的j-k个人。
那么从第i+1个人往后数k-1个人，这k-1个人在i之前入场。那么这k-1个人的怒气值为dp[i+1][i+k-1]。
第i个人的怒气值为ds[i](k-1)
后j-i+1-k个人的怒气值为(sum[j]-sum[i+k-1])k+dp[i+k][j]
这里是由两部分组成的（其中，sum[i]即前i个人的怒气值之和）。
原因是我们我们每次都将区间分割，比如当i=5，j=10，n=20时，在[5,10]区间内，我们没有考虑前4个人的问题，原因就是在较大的[1,20]区间内，我们已经将前四个人产生的怒气值累加进来了。第一部分就是在累加较大区间中前面的人产生的怒气值。而第二部分的dp数组，意义很显然，就是该部分的怒气值。
所以状态转移方程为:
dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+ds[i](k-1)+dp[i+k][j]+(k)(sum[j]-sum[i+k-1]));
值得说明的是，根据k意义的不同，状态转移方程有不同的表达形式，当k的意义为全局[1,n]的第k位时，状态转移方程为:
dp[i][j]=min(dp[i][j],dp[i+1][k]+ds[i](k-i)+dp[k+1][j]+(k-i+1)(sum[j]-sum[k]));

代码

HDU-4283

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 2147483647
int main()
{
    int T;
    scanf("%d",&T);
    for (int t=1;t<=T;t++)
    {
        int N;
        int ds[105];
        int dp[105][105];
        scanf("%d",&N);
        int sum[105];
        memset(sum,0,sizeof(sum));
        for (int i=1;i<=N;i++)
        {
            scanf("%d",&ds[i]);
            sum[i]=sum[i-1]+ds[i];
        }
        memset(dp,0,sizeof(dp));
        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;l++)
        {
            for (int i=1;i<=N-l;i++)
            {
                int j=i+l;
                for (int k=1;k<=j-i+1;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+ds[i]*(k-1)+dp[i+k][j]+(k)*(sum[j]-sum[i+k-1]));
                }
            }
        }
        printf("Case #%d: %d\n",t,dp[1][N]);
    }
    return 0;
}

后记

DP一直都是看题解能看懂自己想无从下手。。希望多做多体会能解决。
今天元宵节啦，晚上去秦淮河畔看人🙃