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 }
