hdu1558 参考答案

   1 /*
   2 hdu 1158
   3 ymc 2008/10/30
   4 题目大意：
   5 有一个项目需要n(n<=12)个月完成，每个月需要的人数已经知道。
   6 另外，雇佣一个人，解雇一个人需要费用，如果雇佣了一个人，
   7 但是没解雇就要付工资。求完成这个项目的最小费用。
   8 分析与解题思路：
   9 题目没有给出人数上限，最不爽这种题目。
  10 其实人数不超过1k(我用1002过的)。
  11 f[i][k]表示第i个月有k个人的时候，项目进行到第i个月的最小费用。
  12 则f[i][k]=min{f[i-1][j]+T+k*salary}
  13 其中T为从第i-1个月的j个人到第i个月的k个人的雇佣或者解雇费用。
  14 */
  15 #include <iostream>
  16 #include <limits>
  17 using namespace std;
  18 const int N=1002;
  19 int f[12][N];
  20 int m[12];
  21 int hire,salary,fire;
  22 int n;
  23 int Max;
  24 void DP()
  25 {
  26     int t;
  27     memset(f,0,sizeof(f));
  28     for(int k=m[0];k<=Max;k++)
  29         f[0][k]=k*(hire+salary);
  30     for(int i=1;i<n;i++)
  31     {
  32         for(int k=m[i];k<=Max;k++)
  33         {
  34             f[i][k]=INT_MAX;
  35             for(int j=m[i-1];j<=Max;j++)
  36             {
  37                 if(j<k)
  38                     t=k*salary+f[i-1][j]+(k-j)*hire;
  39                 else
  40                     t=k*salary+f[i-1][j]+(j-k)*fire;
  41                 if(f[i][k]>t)
  42                     f[i][k]=t;
  43             }
  44         }
  45     }
  46     int ans=INT_MAX;
  47     for(int k=m[n-1];k<=Max;k++)
  48         if(ans>f[n-1][k])
  49             ans=f[n-1][k];
  50     printf("%d\n",ans);
  51 }
  52 int main()
  53 {
  54     while(scanf("%d",&n),n)
  55     {
  56         scanf("%d %d %d",&hire,&salary,&fire);
  57         Max=0;
  58         for(int i=0;i<n;i++)
  59         {
  60             scanf("%d",&m[i]);
  61             if(m[i]>Max)
  62                 Max=m[i];
  63         }
  64         DP();
  65     }
  66 }