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                 else40                     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\n",ans);48     }49     return 0;50 }