又是一道纠结的dp题，做dp快做的崩溃了。。。

 状态表示:    

 Dp[i][j]为前i个月的留j个人的最优解;Num[i]<=j<=Max{Num[i]};

                j>Max{Num[i]}之后无意义,无谓的浪费 记Max_n=Max{Num[i]};

    Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]<<Num[i]

    所以利用Dp[i-1]中的所有项去求Dp[i];

    对于Num[i]<=k<=Max_n,   

 当k<j时, 招聘;  当k>j时, 解雇  然后求出最小值

    Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资);   

代码：

#include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 10000; const int inf = 0xfffffff; int mon[13]; int dp[13][N]; int main() {
    //freopen("data.in", "r", stdin); int m, i, j, k; while(scanf("%d", &m), m)     {
    int hire, fire, salary, max, min, cost;         memset(dp, 0, sizeof(dp));         memset(mon, 0, sizeof(mon));         scanf("%d%d%d", &hire, &salary, &fire);         max = -inf; for(i = 1; i <= m; i++)         {
                scanf("%d", mon + i);             max = max > mon[i] ? max : mon[i];         } for(i = mon[1]; i <= max; i++)             dp[1][i] = (hire+salary) * i; for(i = 2; i <= m; i++)         {
    for(j = mon[i]; j <= max; j++)             {
                    min = inf; for(k = mon[i-1]; k <= max; k++)                 {
    if(k <= j)                         cost = (j-k)*hire + j*salary + dp[i-1][k]; else                         cost = (k-j)*fire + j*salary + dp[i-1][k]; if(min > cost)                         min = cost;                 } //printf("%d\n", min);                 dp[i][j] = min;             }         }         min = inf; for(i = mon[m]; i <= max; i++) if(min > dp[m][i])                 min = dp[m][i];         printf("%d\n", min);     } return 0; }