题目：约翰有h（1≤h≤16）个小时的时间，在该地区有n（2≤n≤25）个湖，这些湖刚好分布在一条路线上，该路线是单向的。约翰从湖1出发，他可以在任一个湖结束钓鱼。但他只能从一个湖到达另一个与之相邻的湖，而且不必每个湖都停留。已知在最初5分钟，湖i预计钓到鱼的数量为fi（fi≥0）。以后每隔5分钟，预计钓到鱼的数量将以常数di（di≥0）递减。如果某个时段预计钓到鱼的数量小于或等于di，那么在下一时段将钓不到鱼。为简单起见，假设没有其它的钓鱼者影响约翰的钓鱼数量。
问题分析：在钓鱼的过程中，访问鱼塘的顺序是单向的，只能从一个鱼塘到相邻的下一个鱼塘，并且从一个鱼塘到相邻的下一个鱼塘路程是要耗费时间的。以5分钟为时间周期，每一个时间周期之后鱼塘一个周期钓到鱼的数量就会减少，即每经过5分钟，fi就会减少对应的di，直到fi小于等于di时，下一周期便不会钓到鱼。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; int n,h,time1[101],t=0,ans=0,sum,temp; struct lake { int num; int lose; bool operator < (const lake &a) const { return num<a.num; } }l[101]; int main() { priority_queue<lake>q; cin>>n>>h; h=h*60/5; for(int i=1;i<=n;i++) cin>>l[i].num; for(int i=1;i<=n;i++) cin>>l[i].lose; time1[0]=0; time1[1]=0; for(int i=1;i<=n-1;i++) cin>>time1[i+1]; for(int i=1;i<=n;i++) { t=0; temp=h; sum=0; for(int j=1;j<=i;j++) t+=time1[j]; temp-=t; for(int j=1;j<=i;j++) q.push(l[j]); while(temp) { lake l1=q.top(); q.pop(); if(l1.num<=0)break; sum+=l1.num; l1.num-=l1.lose; q.push(l1); temp--; } while(!q.empty()) q.pop(); if(sum>ans)ans=sum; } cout<<ans<<endl; return 0; }
样例输入
314 5 61 2 11 2
样例输出
35
贪心策略：每次选择鱼最多的湖钓一次鱼对于每个湖来说，由于在任何时候鱼的数目只和约翰在该湖里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。一共可以钓鱼time次，每次在n个湖中选择鱼最多的一个湖钓鱼。
数媒202 钱
