首页 > 代码库 > HDU 1158 Employment Planning
HDU 1158 Employment Planning
题意:有一公司要工作n个月每个月需要至少p[i]个人工作,每个人的工资固定位m,
每雇佣一个人要花费h,每炒掉一个人要花费f。求完成n个月工作,公司最小的花费。
思路: Dp[i][j]为前i个月的留j个人的最优解;p[i]<=j<=Max{p[i]};
j>Max{p[i]}之后无意义,无谓的浪费 记Max_n=Max{p[i]};
Dp[i-1]中的每一项都可能影响到Dp[i],即使p[i-1]<<p[i]
所以利用Dp[i-1]中的所有项去求Dp[i];
对于p[i]<=k<=Max_n, 当k<j时, 招聘;
当k>j时, 解雇 然后求出最小值
Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资);
#include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath> #include<iostream> #include <queue> #include <stack> #include<algorithm> #include<set> using namespace std; #define INF 1e8 #define eps 1e-8 #define ll __int64 #define maxn 100010 #define mol 1000000007 int dp[15][99999]; int main() { int n,h,m,f; int p[15]; while(scanf("%d",&n)&&n) { scanf("%d%d%d",&h,&m,&f); int maxx=0,minn=99999; for(int i=1;i<=n;i++) { scanf("%d",&p[i]); if(p[i]>maxx) maxx=p[i]; if(p[i]<minn) minn=p[i]; } for(int i=0;i<=n;i++) for(int j=minn;j<=maxx;j++) dp[i][j]=(i==0?0:INF); int fire,hire; for(int i=1;i<=n;i++) { for(int j=p[i];j<=maxx;j++) { if(i==1) dp[i][j]=dp[i-1][j]+j*(m+h); else { for(int k=p[i-1];k<=maxx;k++) { hire=0;fire=0; if(k<j) hire=(j-k)*h; else fire=(k-j)*f; dp[i][j]=min(dp[i][j],dp[i-1][k]+hire+fire+j*m); } } } } int ans=INF; for(int i=p[n];i<=maxx;i++) if(dp[n][i]<ans) ans=dp[n][i]; printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。