题解:雇佣计划
程序员文章站
2022-03-20 17:24:05
题目描述: 一位管理员项目的经理想要确定每个月需要的工人,他当然知道每月所需要的最少工人数。当他雇佣或解雇一个工人时,会有一此额外的支出。一旦一个工人被雇佣,即使他不工作,他也将得到工资。这位经理知道雇佣一个工人的费用,解雇一个工人的费用和一个工人的工资。现在他在考虑一个问题:为了把项目的费用控制在 ......
题目描述:
一位管理员项目的经理想要确定每个月需要的工人,他当然知道每月所需要的最少工人数。当他雇佣或解雇一个工人时,会有一此额外的支出。一旦一个工人被雇佣,即使他不工作,他也将得到工资。这位经理知道雇佣一个工人的费用,解雇一个工人的费用和一个工人的工资。现在他在考虑一个问题:为了把项目的费用控制在最低,他将每月雇佣或解雇多少个工人。
输入格式:
共三行。
第一行为月数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.验证完毕,程序无误。
上一篇: 学习servlet笔记(一)