【HDU 5887】Herbs Gathering

传送门戳这里

题目描述

Collecting one's own plants for use as herbal medicines is perhaps one of the most self-empowering things a person can do, as it implies that they have taken the time and effort to learn about the uses and virtues of the plant and how it might benefit them, how to identify it in its native habitat or how to cultivate it in a garden, and how to prepare it as medicine. It also implies that a person has chosen to take responsibility for their own health and well being, rather than entirely surrender that faculty to another. Consider several different herbs. Each of them has a certain time which needs to be gathered, to be prepared and to be processed. Meanwhile a detailed analysis presents scores as evaluations of each herbs. Our time is running out. The only goal is to maximize the sum of scores for herbs which we can get within a limited time.

解题思路

代码

1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<map>
 6 #define LL long long 
 7 using namespace std;
 8 LL w[1100],v[1100],m;
 9 int n;
10 int main(){
11     while(~scanf("%d%lld",&n,&m)){
12         for(register int i=1;i<=n;i++){
13             scanf("%lld%lld",&w[i],&v[i]); 
14         }
15         map<LL,LL>dp;
16         map<LL,LL>::iterator it;
17         dp[0]=0;
18         for(register int i=1;i<=n;i++){
19             it=dp.end(); it--;
20             while(1){
21                 LL W=it->first;
22                 LL V=it->second;
23                 if(W+w[i]<=m)dp[W+w[i]]=max(dp[W+w[i]],dp[W]+v[i]);
24                 if(it==dp.begin())break;
25                 it--;
26             }
27             LL t=0;
28             it=dp.begin();
29             for(it=dp.begin();it!=dp.end();){
30                 if(it->second!=0&&it->second<=t){
31                     dp.erase(it++);
32                 }
33                 else t=it->second,it++;
34             }
35         }
36         LL ans=0;
37         for(it=dp.begin();it!=dp.end();it++){
38             ans=max(ans,it->second);
39         }
40         cout<<ans<<endl;
41     }
42 }