题解:雇佣计划
2019-08-16 07:50:26来源:博客园 阅读 ()
题解:雇佣计划
题目描述:
一位管理员项目的经理想要确定每个月需要的工人,他当然知道每月所需要的最少工人数。当他雇佣或解雇一个工人时,会有一此额外的支出。一旦一个工人被雇佣,即使他不工作,他也将得到工资。这位经理知道雇佣一个工人的费用,解雇一个工人的费用和一个工人的工资。现在他在考虑一个问题:为了把项目的费用控制在最低,他将每月雇佣或解雇多少个工人。
输入格式:
共三行。
第一行为月数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.验证完毕,程序无误。
原文链接:https://www.cnblogs.com/hihocoder/p/user.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:费马小定理入门
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash