首页 > 代码库 > hdu--1158--dp
hdu--1158--dp
不会做啊 这么水的dp =-=
怨死 。。。。 touch me
我下面内容 都是来自 传送
dp[i][j]表示前i个月最后一个月的总人数为j所花的最小费用
状态移动方程:dp[i][j] = min{dp[i-1][k] + cost[i][j]},其中cost[i][j]是第i月的花费,
1~当k<=j时，第i个月请了人所以cost[i][j] = j*salary + (j-k)*hire
2~当k>j时，第i个月炒了人，所以cost[i][j] = j*salary + (k-j)*fire
输入时记录了最多需要的人数。
因为他给的是每个月最少需要的人数，所以for(该月需要的最少人数——max_people)而不是for(1——该月需要的最少人数)
直接初始化第一个月。
1 #include<stdio.h> 2 #include<string.h> 3 4 const int INF=99999999; 5 6 int dp[15][10010]; 7 int people[15]; 8 9 int main(){10 11 //freopen("input.txt","r",stdin);12 13 int n;14 int hire,salary,fire;15 while(scanf("%d",&n) && n){16 scanf("%d%d%d",&hire,&salary,&fire);17 int max_people=0;18 int i,j,k;19 for(i=1;i<=n;i++){20 scanf("%d",&people[i]);21 if(max_people<people[i])22 max_people=people[i];23 }24 for(i=people[1];i<=max_people;i++) //初始化第一个月25 dp[1][i]=i*salary+i*hire;26 int min;27 for(i=2;i<=n;i++){28 for(j=people[i];j<=max_people;j++){29 min=INF; //有了这个前面就不需要用O（n^2）初始化dp了。30 for(k=people[i-1];k<=max_people;k++)31 if(min>dp[i-1][k]+(j>=k?(j*salary+(j-k)*hire):(j*salary+(k-j)*fire)))32 min=dp[i-1][k]+(j>=k?(j*salary+(j-k)*hire):(j*salary+(k-j)*fire));33 dp[i][j]=min;34 }35 }36 min=INF;37 for(i=people[n];i<=max_people;i++)38 if(min>dp[n][i])39 min=dp[n][i];40 printf("%d\n",min);41 }42 return 0;43 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。