hdu 1158(dp)

青旅半醒 2022-08-20 14:19 128阅读 0赞

题意：

一项工程需要n个月完成，每个月最少需要的员工数为a\[i\]，雇佣一个员工和开除一个员工的费用为hire与fire，每个员工每个月的工资为salary，现在要求完成这项工程最少的花费。n<=12

分析：

由于这道题目没有告诉我们a\[i\]的范围，所以我想了很久迟迟没有动手，因为想到一个方法的时间复杂度为max(a\[i\])^2\*n , 实在是不知道怎么办了就用这种方法写了，WA了几次就过了，应该是a\[i\]还是比较小的。

我们用dp\[i\]\[j\]表示在第i个月雇佣j个人的最小花费，j >= a\[i\] .  状态转移方程在代码里面，比较简单一看就可以明白。分为这个月的员工数比上个月的员工数大和小两种情况。

PS：之前一直觉得最小的情况一定是最后一个月恰好雇佣a\[i\]个人就好了，想着要是多了的话不是白给工资吗，一直WA，突然想明白了因为有可能开除一个人的花费比他的salary还有多，所以最后一个月多几个人可能总花费还少一些，反正不考虑最后一个月之后这些人的花费情况。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    #define inf 100000000
    
    const int maxn = 10005;
    int dp[12][maxn];
    //dp[i][j]表示的是第i个月有j个员工的总花费
    int a[12];
    int hire,salary,fire;
    
    int main()
    {
        int n ;
        while(scanf("%d",&n)&&n)
        {
            scanf("%d%d%d",&hire,&salary,&fire);
            int maxx = 0 ;
            for(int i = 0 ; i < n ; i++)
            {
                scanf("%d",&a[i]);
                maxx = max(maxx,a[i]);
            }
            for(int i = a[0] ; i <= maxx ; i++)
            {
                dp[0][i] = i*salary + i*hire ;
            }
            for(int i = 1 ; i < n ; i++)
            {
                for(int j = a[i] ; j <= maxx ; j++)
                {
                    dp[i][j] = inf ;
                    for(int k = a[i-1] ; k <= maxx ; k++)
                    {
                        if(k<=j)dp[i][j] = min(dp[i][j] , dp[i-1][k]+j*salary+(j-k)*hire) ; //上个月人少，需要hire
                        else dp[i][j] = min(dp[i][j] , dp[i-1][k]+j*salary+(k-j)*fire) ;    //上个月人多，需要fire
                    }
                }
            }
            int ans = inf ;
            for(int i = a[n-1] ; i <= maxx ; i++)
            {
                ans = min(ans,dp[n-1][i]) ;
            }
            printf("%d\n",ans);
        }
        return 0;
    }