hdu 1158 dp

 1 /*
 2 题目大意：给n个月工作需要的人数，雇佣一个需要花hire
 3 每个月的薪水是salary，解雇一个需要fire
 4 求完成所有工作的最小费用
 5 dp(i,j)表示第i个月雇佣j员工的最小费用
 6 */
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <cstring>
10 using namespace std;
11 
12 const int maxn=15;
13 const int INF=1<<30;
14 int dp[maxn][300],num[maxn];
15 inline int max(int a,int b){return a>b?a:b;}
16 inline int min(int a,int b){return a<b?a:b;}
17 int main()
18 {
19     int n,hire,salary,fire,i,j,k,Max;
20     while(scanf("%d",&n),n)
21     {
22         scanf("%d%d%d",&hire,&salary,&fire);
23         Max=0;
24         for(i=1;i<=n;i++)
25         {
26             scanf("%d",num+i);
27             Max=max(num[i],Max);
28         }
29         for(i=0;i<=Max;i++)
30             dp[1][i]=(hire+salary)*i;
31         for(i=2;i<=n;i++)
32         {
33             for(j=num[i];j<=Max;j++)
34             {
35                 int temp=INF;
36                 for(k=num[i-1];k<=Max;k++)
37                 if(k<j)
38                     temp=min(temp,dp[i-1][k]+hire*(j-k)+salary*j);
39                 else
40                     temp=min(temp,dp[i-1][k]+fire*(k-j)+salary*j);
41                 dp[i][j]=temp;
42             }
43         }
44         int ans=INF;
45         for(i=num[n];i<=Max;i++)
46             ans=min(ans,dp[n][i]);
47         printf("%d
",ans);
48     }
49     return 0;
50 }