Blog·Tanky WooABOUTRSS

HDU/HDOJ 1158 Employment Planning(DP)

02 Feb 2012
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1158

不知道为啥,这道DP把我脑袋快转晕了,有个地方想到了,可就是转不过去,真晕菜。

不过历经2小时,还是写出来了,这花的时间,真囧。。。。

分析:

DP,这一题数据范围没给出,不严谨。经测试,公认数量开105就行了,工资我现开始开0xffff,然后WA了,接着开了0x3ffffff,就AC了。

数组dp[i][j]表示第i个月员工数为j的总花费。

这题逐层(月)考虑,在上一层顺序遍历每一个dp[i-1][j] != INF的:

1.如果上一层(月)(即j)比本层(月)要求的人数(即man[i])少,则只需要雇佣相差的人数

2.如果上一层比本层要求人数多,则在man[i]和j之间,dp各个情况就行。

说不清楚~~具体看代码:

/* Tanky Woo   
 * HDU 1158 DP   
 * 2012.2.2   
 */  
#include <iostream>
using namespace std;

int mo;
int hire, salary, fire;
int man[15];
int dp[15][105];
const int INF = 0x3ffffff;

int SML(int a, int b)
{
    return a<b? a:b;
}

int main()
{
    while(cin >> mo && mo)
    {
        cin >> hire >> salary >> fire;

        int _min=INF, _max=0;
        for(int i=1; i<=mo; ++i)
        {
            cin >> man[i];
            if(man[i]>_max) _max = man[i];
            if(man[i]<_min) _min = man[i];
        }
        //memset(dp, 0, sizeof(dp));
        for(int i=1; i<=mo; ++i)
            for(int j=0; j<=105; ++j)
                dp[i][j] = INF;

        dp[1][man[1]] = man[1]*(hire + salary);
        for(int i=2; i<=mo; ++i)
        {
            for(int j=_min; j<=_max; ++j)
            {
                if(dp[i-1][j] == INF)
                    continue;
                if(man[i] >= j)
                    dp[i][man[i]] = SML(dp[i][man[i]], dp[i-1][j]+hire*(man[i]-j)+salary*man[i]);
                else
                    for(int k=man[i]; k<=j; ++k)
                        dp[i][k] = SML(dp[i][k], dp[i-1][j]+fire*(j-k)+salary*k);
            }
        }
        int imin = INF;
        for(int i=_min; i<=_max; ++i)
            if(imin > dp[mo][i])
                imin = dp[mo][i];
        cout << imin << endl;
    }
    return 0;
}