1373：鱼塘钓鱼(fishing）
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：
鱼塘编号每1分钟能钓到的鱼的数量（1..1000）每1分钟能钓鱼数的减少量（1..100）当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）11023214453206441654593
即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……
给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。
【输入】
共5行，分别表示：
第1行为N；
第2行为第1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；
第3行为每过1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；
第4行为当前鱼塘到下一个相邻鱼塘需要的时间；
第5行为截止时间T。
【输出】
一个整数（不超过2^31−1），表示你的方案能钓到的最多的鱼。
【输入样例】
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
【输出样例】
76
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. using namespace std; 5. int n,fish[105],reduce_fish[105],minute[105]; 6. int size,heap[100005];//大堆 7. int T,hlake[100005]; 8. void put(int x,int lake){//增加元素 9. int i,j,t; 10. size++;heap[size]=x; 11. hlake[size]=lake;i=size; 12. while(i>1){//向上调整 13. j=i/2; 14. if(heap[i]<=heap[j]) return;//子结点小于等于父结点 返回 15. //子结点比父结点大 就交换 16. t=heap[i];heap[i]=heap[j];heap[j]=t; 17. t=hlake[i];hlake[i]=hlake[j];hlake[j]=t; 18. i=j; 19. } 20. } 21. void Heap(int erw){//将堆中第i个元素向下调整 22. int i=erw,j,t; 23. while(i*2<=size){ 24. j=i*2; 25. if(j<size && heap[j+1]>heap[j]) j++;//右孩子大于左孩子 使用右孩子 26. if(heap[i]>=heap[j]) return;//父结点大于等于子结点 返回 27. //父结点小于子结点 交换 28. t=heap[i];heap[i]=heap[j];heap[j]=t; 29. t=hlake[i];hlake[i]=hlake[j];hlake[j]=t; 30. i=j; 31. } 32. } 33. int main() 34. { 35. int i,j,m,p=0,ans=0; 36. cin>>n; 37. for(i=1;i<=n;i++) cin>>fish[i]; 38. for(i=1;i<=n;i++) cin>>reduce_fish[i]; 39. for(i=1;i<=n-1;i++) cin>>minute[i]; 40. cin>>m; 41. for(i=1;i<=n;i++){//枚举最后一个到达的鱼塘 42. T=m-p; 43. int sum=0;size=0; 44. for(j=1;j<=i;j++) put(fish[j],j);//入堆 45. while(T>0 && heap[1]>0){//时间没有结束 且这个鱼塘里还有鱼 46. sum+=heap[1];//增加大堆顶 47. heap[1]-=reduce_fish[hlake[1]];//鱼塘鱼量减少 48. Heap(1);//调整堆 49. T--;//时间减少 50. } 51. if(sum>ans) ans=sum;//更新最大值 52. p+=minute[i]; //调整到下一个鱼塘 53. } 54. cout<<ans; 55. return 0; 56. }
