当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 题解：雇佣计划

题解：雇佣计划

2019年07月19日  | 移动技术网IT编程  | 我要评论

司法所着装,快乐大本营花样少男少女,肥城桃花节

题目描述：

一位管理员项目的经理想要确定每个月需要的工人，他当然知道每月所需要的最少工人数。当他雇佣或解雇一个工人时，会有一此额外的支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一个工人的工资。现在他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇佣或解雇多少个工人。

输入格式：

共三行。
第一行为月数n（不超过12）。
第二行含雇佣一个工人的费用，一个工人的工资和解雇一个工人的费用（<101）。
第三行含n个数，分别表示每月最少需要的工人数(<1001)每个数据之间用空格相隔。

输出格式：

仅一行，表示项目的最小总费用。

样例输入一：

3
4 5 6
10 9 11

样例输出一：

199

样例输入二：

3
4 5 6
10 9 8

样例输出二：

186

算法标签

贪心思路：

第 1月雇佣所需的工人数。此后只有三种情况：
1.工人缺少（雇佣）
2.工人恰好（照常发工资）
3.工人冗余。（①解雇 ②留用）

贪心代码一：

（不加注释，用于复制）

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    freopen("user.in","r",stdin),freopen("user.out","w",stdout);
    int n,a,b,c,n[15],ans,hehe,haha,res1,res2,i,j,k;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    for (i=1;i<=n;++i) scanf("%d",&n[i]);
    for (ans=(a+b)*n[1],i=2;i<=n;++i)
    {
        ans+=b*n[i],hehe=n[i]-n[i-1];
        if (hehe==0) continue;
        if (hehe>0) ans+=a*hehe;
        if (hehe<0)
        {
            for (hehe=0-hehe,j=1;j<=hehe;++j)
            {
                haha=n[i]+1,res1=0;
                for (k=i+1;k<=n;++k)
                    if (n[k]>=haha) {res1=a;break;}
                res1+=c,res2=b*(k-i);
                if (res1>=res2) ++n[i],ans+=b;
                else {ans+=c*(hehe-j+1);break;}
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

贪心代码二：

（加注释，便于理解）

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    freopen("user.in","r",stdin),freopen("user.out","w",stdout);
    int n,a,b,c,n[15],ans,hehe,haha,res1,res2,i,j,k;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    for (i=1;i<=n;++i) scanf("%d",&n[i]);
    for (ans=(a+b)*n[1],i=2;i<=n;++i)
    {
        ans+=b*n[i],hehe=n[i]-n[i-1];
        if (hehe==0) continue;//情况二，不多也不少
        if (hehe>0) ans+=a*hehe;//情况一，少了
        if (hehe<0)//情况三，有多余的
        {
            for (hehe=0-hehe,j=1;j<=hehe;++j)//枚举每一位多余的工人，计算出是否有必要解雇
            {
                haha=n[i]+1,res1=0;
                for (k=i+1;k<=n;++k)
                    if (n[k]>=haha) {res1=a;break;}//下一次雇佣
                res1+=c,res2=b*(k-i);//res1表示解雇的钱数，res2表示不解雇的工资
                if (res1>=res2) ++n[i],ans+=b;//不解雇，本月工人数加一，给他发工资
                else {ans+=c*(hehe-j+1);break;}//解雇，解雇所支付的钱数
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

（个人认为动归易理解，直接上代码）

动归代码一：

（无注释版）

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    freopen("user.in","r",stdin),freopen("user.out","w",stdout);
    int n,a,b,c,maxn,minn,sum,now,last,ans,n[15],f[2][1200],inf=99999999,i,j,k;
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&n[1]);
    for (maxn=n[1],minn=n[1],i=2;i<=n;++i)
    {
        scanf("%d",&n[i]);
        maxn=max(maxn,n[i]),minn=min(minn,n[i]);
    }
    for (i=minn;i<n[1];++i) f[1][i]=inf;
    for (i=n[1];i<=maxn;++i) f[1][i]=i*(a+b);
    for (now=1,i=2;i<=n;++i)
    {
        last=now,now=!now;
        for (j=minn;j<n[i];++j) f[now][j]=inf;
        for (j=n[i];j<=maxn;++j)
        {
            f[now][j]=f[last][j];
            for (k=minn;k<j;++k) f[now][j]=min(f[now][j],f[last][k]+a*(j-k));
            for (k=j+1;k<=maxn;++k) f[now][j]=min(f[now][j],f[last][k]+c*(k-j));
            f[now][j]+=b*j;
        }
    }
    ans=f[now][n[n]];
    for (i=n[n]+1;i<=maxn;++i) ans=min(ans,f[now][i]);
    printf("%d\n",ans);
    return 0;
}

动归代码二：

（有注释版）

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    freopen("user.in","r",stdin),freopen("user.out","w",stdout);
    int n,a,b,c,maxn,minn,sum,now,last,ans,n[15],f[2][1200],inf=99999999,i,j,k;
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&n[1]);
    for (maxn=n[1],minn=n[1],i=2;i<=n;++i)
    {
        scanf("%d",&n[i]);
        maxn=max(maxn,n[i]),minn=min(minn,n[i]);//循环上界与下界
    }
    for (i=minn;i<n[1];++i) f[1][i]=inf;//不可行，赋最大值
    for (i=n[1];i<=maxn;++i) f[1][i]=i*(a+b);//第一个月雇佣i人的钱数
    for (now=1,i=2;i<=n;++i)//从第二个月开始算
    {
        last=now,now=!now;//滚动数组优化内存空间
        for (j=minn;j<n[i];++j) f[now][j]=inf;//不可行，赋最大值
        for (j=n[i];j<=maxn;++j)//本月实际雇佣数
        {
            f[now][j]=f[last][j];//不雇佣也不解雇（刚刚好，不用管）
            for (k=minn;k<j;++k) f[now][j]=min(f[now][j],f[last][k]+a*(j-k));//雇佣j-k人（设上一个月雇佣k人，应该雇佣本月实际雇佣数j减去k的工人数）
            for (k=j+1;k<=maxn;++k) f[now][j]=min(f[now][j],f[last][k]+c*(k-j));//解雇k-j人（设上一个月雇佣k人，应该解雇多于本月实际雇佣数j的工人数）
            f[now][j]+=b*j;//发工资
        }
    }
    ans=f[now][n[n]];//第n月至少n人
    for (i=n[n]+1;i<=maxn;++i) ans=min(ans,f[now][i]);
    printf("%d\n",ans);
    return 0;
}

验证

1. 生成随机数：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{
    srand((unsigned)time(0));
    freopen("user.in","w",stdout);
    int a,b,c,n;
    a=rand()%100+1,b=rand()%100+1,c=rand()%100+1;
    printf("12\n%d %d %d\n",a,b,c);
    for (int i=1;i<=12;++i)
    {
        n=rand()%500+500;
        printf("%d ",n);
    }
    printf("\n");
    return 0;
}

2.对拍：

@echo off
:loop
test.exe
user.exe
user2.exe
fc user.out user2.out &&goto loop
exit 0

3.验证完毕，程序无误。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网