ACM题目之 招聘计划

《ACM题目之 招聘计划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、招聘计划TimeLimit:5000MS MemoryLimit:65536KTotalSubmit:97Accepted:8DescriptionAprojectmanagerwantstodeterminethenumberoftheworkersneededineverymonth.Hedoesknowtheminimalnumberoftheworkersneededineachmonth.Whenhehiresorfiresaworker,therewillbesomeextracost.Onceaworkerishired,hewillgetthesalaryevenifheis

2、notworking.Themanagerknowsthecostsofhiringaworker,firingaworker,andthesalaryofaworker.Thenthemanagerwillconfrontsuchaproblem:howmanyworkershewillhireorfireeachmonthinordertokeepthelowesttotalcostoftheproject.一个工程部经理想确定每个月的员工的总人数。他知道每个月员工人数的最小值。当他雇用或解雇一个员工时，将有一笔额外的开销。一旦，解雇一个员工，即便他没有工作，他将得到这个月的薪水。经理知

3、道解雇工人和雇用工人的开销，以及工人的薪水。因此，这个经理面临这样一个问题：他每个月将雇用或解雇多少员工才能使工程部的总开销最低。InputTheinputmaycontainseveraldatasets.Eachdatasetcontainsthreelines.Firstlinecontainsthemonthsoftheprojectplanedtousewhichisnomorethan12.Thesecondlinecontainsthecostofhiringaworker,theamountofthesalary,thecostoffiringaworker.Thethird

4、linecontainsseveralnumbers,whichrepresenttheminimalnumberoftheworkersneededeachmonth.Theinputisterminatedbylinecontainingasingle‘0’。输入数据可以包含若干数据集。每个数据集包含3行。第一行输入这个工程计划的工期(以月为单位)，不超过12个月。第二行包含雇用一个工人的开销，薪水数，和解雇一个工人的开销。第三行包括多个数据，表示每个月需要的最小的工人数。在最后一行输入0表示结束。OutputTheoutputcontainsoneline.Theminimaltota

5、lcostoftheproject.结果只有一行，为这个项目的最小总开销。SampleInput3456109110SampleOutput199EmploymentPlanning条件DP状态：dp[i][j]前i个月，并且第i个月留下j个人的最小花费j>=num[i]&&j<=MaxNumMaxNum=max{num[i]}i>=1&&i<=n转移方程：dp[i][j]=min{dp[i-1][k]+决策代价+j*salary}k>=num[i-1]&&k<=MaxNum注：上面的工资应该加的是第j个月的，因为状态表示是到前i 个月为止k>j决策代价(k-j)*firek

6、-k)*hire边界条件及初始化：dp[i][j]=j*(salary+hire)j>=num[i]&&j<=MaxNum&&i>=1&&i<=n这个初始化是错的，因为其实只有第一个月是可以确定的，其它的都是未知的，你不能直接提前赋值，否则的话，可能在决策枚举进行阶段转移的时候，这个状态是值是不够大的，那么转移到下一个阶段的值不一定是最优的，这个初始化要注意下正确的边界条件和初始化是：dp[1][j]=j*(salary+hire)j>=num[1]&&j<=MaxNum答案：ans=min{dp[n][j]}j>=num[n]&&j<=MaxNum附AC代码：#include

7、h>#include#defineinf1000000intp,f,h;inttran(inti,intj){if(i>j)return(i-j)*f;if(i