hdu 1158(很好的一道dp题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1158

很不错的一道题，可是一开始没看出来。。。刷的题不够多！！！

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 const int inf=1e9;
 4 const int N=14;
 5 using namespace std;
 6 int num[N];
 7 int dp[N][111];//dp[i][j]表示前i个月（包括第i个月）招了j个员工的最小花费
 8 
 9 
10 int main(){
11     int n;
12     while(~scanf("%d",&n)&&n){
13         int hire,salary,fire;
14         scanf("%d%d%d",&hire,&salary,&fire);
15         int maxnum=0;
16         for(int i=1;i<=n;i++){
17             scanf("%d",&num[i]);
18             maxnum=max(maxnum,num[i]);
19         }
20         for(int i=num[1];i<=maxnum;i++){
21             dp[1][i]=(salary+hire)*i;//初始化要注意啊！！！
22         }
23         for(int i=2;i<=n;i++){
24             for(int j=num[i];j<=maxnum;j++){
25                 int MIN=inf;
26                 for(int k=num[i-1];k<=maxnum;k++){
27                     if(k<j){
28                         MIN=min(MIN,dp[i-1][k]+(j-k)*hire+j*salary);
29                     }else {
30                         MIN=min(MIN,dp[i-1][k]+(k-j)*fire+j*salary);
31                     }
32                 }
33                 dp[i][j]=MIN;
34             }
35         }
36         int ans=inf;
37         for(int i=num[n];i<=maxnum;i++){
38             ans=min(ans,dp[n][i]);
39         }
40         printf("%d\n",ans);
41     }
42     return 0;
43 }