首页 > 代码库 > hdu--1158--dp

hdu--1158--dp

2024-07-14 15:49:39   212人阅读

不会做啊 这么水的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 }
View Code

 


联系
我们