1 //Accepted    232 KB    0 ms 2 //DP 3 //dp[i][j]表示第i个月人数为a[j]时的最小花费 4 //dp[i][j]=min(dp[i][j],dp[i-1][k]+hire*(a[j]-a[k])+pay*a[j]) a[j]>a[k]时 5 //dp[i][j]=min(dp[i][j],dp[i-1][k]+fire*(a[k]-a[j])+pay*a[j]) a[k]>=a[j]时 6 //a[i] 表示第i个月要用到的最少人数 7 // 8 #include <cstdio> 9 #include <cstring>10 #include <iostream>11 using namespace std;12 const int imax_n = 13;13 const int inf = 100000000;14 int a[imax_n];15 int dp[imax_n][imax_n];16 int hire,fire,pay;17 int n;18 19 int min(int a,int b)20 {21     return a>b?b:a;22 }23 int Dp()24 {25     for (int i=0;i<=n;i++)26     for (int j=0;j<=n;j++)27     dp[i][j]=inf;28     dp[0][0]=0;29     for (int i=1;i<=n;i++)30     {31         for (int j=0;j<=n;j++)32         if (a[j]>=a[i])33         {34             for (int k=0;k<=n;k++)35             {36                 if (a[k]>a[j])37                 dp[i][j]=min(dp[i][j],dp[i-1][k]+fire*(a[k]-a[j])+pay*a[j]);38                 else39                 dp[i][j]=min(dp[i][j],dp[i-1][k]+hire*(a[j]-a[k])+pay*a[j]);40             }41         }42     }43     int ans=inf;44     for (int i=0;i<=n;i++)45     ans=min(ans,dp[n][i]);46     printf("%d\n",ans);47     return ans;48 }49 int main()50 {51     while (scanf("%d",&n),n)52     {53         scanf("%d%d%d",&hire,&pay,&fire);54         for (int i=1;i<=n;i++)55         scanf("%d",&a[i]);56         a[0]=0;57         Dp();58     }59     return 0;60 }