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
",ans);

41     }

42     return 0;

43 }