首页 > 代码库 > POJ_1042_贪心
POJ_1042_贪心
题目描述：
每组数据给你n个胡，h小时时间，每个湖一次可钓鱼数量，每个湖每次钓鱼后下次可钓鱼数量的减少量，从每个湖到下一个湖所需时间。求最大钓鱼量。
要注意的是，刚开始在第一个湖，每次移动只能往下一个湖移动，每次钓鱼数量最多可减少到0。
若多种情况钓鱼数量一样，则取前面的湖钓鱼次数最多的。
思路：
先把时间统一。
可以按跑了多少个湖分n种情况，也就是最后呆在哪个湖。
对于每一种情况，减去跑路的时间，总的钓鱼的时间是一样的，问题就变成了，怎么在跑过的湖分配时间，使效益最大。
贪心，每次取最大值，湖的状态更新之后，再取最大值......
一直到时间耗光，上面的值相加就是这种情况下的钓鱼最大数量。
然后每种情况取最大值便是最终答案，另外，每种情况还需要一个数组保存每个湖钓鱼次数。
最后要注意的是，钓鱼数量一样取前面的湖钓鱼次数最多的，若当前每个湖钓鱼数量均为0，可以直接把剩余时间全部投入第一个湖，结束此次过程。
#include<iostream>#include<cstdio>using namespace std;int n,h,t[26],f[26],d[26],ans[26];int main(){ while(cin >> n && n) { cin >> h; h = h*60; int i,j; for(i = 1;i <= n;i++) cin >> f[i]; for(i = 1;i <= n;i++) cin >> d[i]; for(i = 1;i < n;i++) cin >> t[i]; int sum = -1; for(i = 1;i <= n;i++) { int point,temp_h = h,temp_sum = 0,temp_f[26],temp_ans[26] = {0}; for(j = 1;j <= n;j++) temp_f[j] = f[j]; while(temp_h) { int maxf = 0; for(j = 1;j <= i;j++) { if(temp_f[j] > maxf) { maxf = temp_f[j]; point = j; } } if(maxf) { temp_ans[point] += 5; temp_sum += temp_f[point]; if(temp_f[point] >= d[point]) temp_f[point] -= d[point]; else temp_f[point] = 0; } else { temp_ans[1] += temp_h; break; } temp_h -= 5; } if(h > t[i]*5) { h -= t[i]*5; } else { h = 0; } if(temp_sum > sum) { for(j = 1;j <= n;j++) { ans[j] = temp_ans[j]; } sum = temp_sum; } } for(i= 1;i < n;i++) cout << ans[i] << ", "; cout << ans[n] << endl; cout << "Number of fish expected: " << sum << endl; cout<<endl; } return 0;}
POJ_1042_贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。