首页 > 代码库 > poj1042 Gone Fishing
poj1042 Gone Fishing
题目来源:http://poj.org/problem?id=1042
题目大意:一个人在一个打算在编号1~n的湖里钓鱼,钓鱼是单向走的,不能往回走。给你n个湖,每个湖初始鱼的数量pi每次每个湖钓鱼后鱼的减少量di,第i个湖到第i+1湖的距离时间ti(单位是5min。。。),这个人可以在任何湖停止钓鱼求如何钓鱼才能才能在h小时内钓鱼量最多输出在每个湖钓鱼的时间。相同钓鱼量情况下,输出湖编号小的用时多的时间。
题目思路:用贪心+枚举即可。在枚举的大循环下,每一种枚举情况采用贪心计算出最优的钓鱼情况。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int ans[30][30],f[30],d[30],t[30]; int main() { int h,n; cin>>n; while(true) { if(n==0) break; cin>>h; h*=12; memset(ans,0,sizeof(ans)); memset(f,0,sizeof(f)); memset(t,0,sizeof(t)); memset(d,0,sizeof(d)); for(int i=1;i<=n;++i) { scanf("%d",&f[i]); } for(int i=1;i<=n;++i) { scanf("%d",&d[i]); } for(int i=1;i<n;++i) { scanf("%d",&t[i]); } int ht,ft[30]; for(int ed=1;ed<=n;++ed)//枚举从第一个湖开始走 { memset(ft,0,sizeof(ft)); for(int i=1;i<=ed;++i) { ft[i]=f[i]; }//ft作为f的临时记录 ht=h;//记录剩余时间 for(int i=1;i<ed;++i) { ht-=t[i];//每一种枚举情况下除去走路花费的时间 } //剩余的时间来钓鱼 int k,emp=1;//emp代表当前的湖 while(ht>0&&emp<=ed)//时间用完或湖空为止 { k=1; for(int j=emp;j<=ed;++j) { if(ft[j]>ft[k]) { k=j; } }//找出最优的湖 //用ans[池塘编号][0]表示收获量,其余元素表示需要的时间 ans[ed][0]+=ft[k];//此次收获+ft[k] ++ans[ed][k];//记录在k湖花费了1单位时间 --ht;//时间消耗1单位 ft[k]-=d[k];//鱼的总量减少 ft[k]=ft[k]>0?ft[k]:0; for(int j=emp;j<=ed;++j) { if(ft[j]==0) ++emp;//若有湖空了,则进入下一个湖 else break; }//检查是否ed前的湖都已空 } if(ht>0) ans[ed][1]+=ht;//若尝试了所有的湖后时间有剩余 } int a=1; for(int i=2;i<=n;++i) { if(ans[i][0]>ans[a][0]) a=i; }//找出收益最大的方案 for(int i=1;i<=n;++i) { cout<<ans[a][i]*5;//输出所有的池塘所待的时间 if(i!=n) cout<<", "; } cout<<endl; cout<<"Number of fish expected: "<<ans[a][0]<<endl; cin>>n; if(n!=0) cout<<endl; } return 0; }
poj1042 Gone Fishing
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。