//DP[i][j]表示第i月用j个工人的最小花费 //枚举+DP,k为上月使用的工人数 //if(j <= k) // cost = (hiring*(j-k)) + s*j + DP[i-1][k]; //else // cost = (firing*(k-j)) + s*j + DP[i-1][k]; //枚举j和k,将cost的最小值填入DP[i][j]; //结果为DP[month][....]的最小值 #include <iostream> #include <cstring> using namespace std; int month; int hiring,firing,salary; int worker[13]; int DP[13][1000]; int main() { while(cin>>month,month != 0) { cin>>hiring>>salary>>firing; int maxj = 0; for(int i = 1; i <= month; i++) { cin>>worker[i]; if(maxj < worker[i]) { maxj = worker[i]; } } for(int i = worker[1]; i <= maxj; i++) { DP[1][i] = (hiring*i + salary*i); } int cost = 0; for(int i = 2; i <= month; i++) { for(int j = worker[i]; j <= maxj; j++) { int mins = 999999999; for(int k = worker[i-1]; k <= maxj; k++) { if(j >= k) { cost = (hiring*(j-k)) + salary*j + DP[i-1][k]; } else { cost = (firing*(k-j)) + salary*j + DP[i-1][k]; } if(cost < mins ) { mins = cost; } } DP[i][j] = mins; } } int min = 999999999; for(int i = worker[month]; i <= maxj; i++) { if(min > DP[month][i]) { min = DP[month][i]; } } cout<<min<<endl; } return 0; }