首页 > 代码库 > hdu 1158 Employment Planning（DP）
hdu 1158 Employment Planning（DP）
题意：
有一个工程需要N个月才能完成。（n<=12）
给出雇佣一个工人的费用、每个工人每个月的工资、解雇一个工人的费用。
然后给出N个月所需的最少工人人数。
问完成这个项目最少需要花多少钱。
思路：
将(i,num)：【第i个月拥有num个工人 】看成一个状态。那么就想到用DP。
看代码
代码：
struct node{ int minNum, maxNum;}month[15];int n;int hire,salary,fire;int dp[15][505];int main(){ int n; while(scanf("%d",&n),n){ scanf("%d%d%d",&hire,&salary,&fire); int maxs=-1; rep(i,1,n){ scanf("%d",&month[i].minNum); maxs=max( maxs,month[i].minNum); } rep(i,1,n){ month[i].maxNum=maxs; } mem(dp,inf); rep(i,month[1].minNum,month[1].maxNum){ dp[1][i]=i*(hire+salary); } rep(i,2,n){ rep(j,month[i].minNum,month[i].maxNum){ //这个月招人数 rep(k,month[i-1].minNum,month[i-1].maxNum){ //上个月招人数 int dd; if(j>k){ dd=(j-k)*hire; }else{ dd=(k-j)*fire; } dp[i][j]=min( dp[i][j],dp[i-1][k]+salary*j+dd ); } } } int ans=inf; rep(i,month[n].minNum,month[n].maxNum){ ans=min( ans,dp[n][i] ); } printf("%d\n",ans); } return 0;}
hdu 1158 Employment Planning（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。