题目链接：https://vjudge.net/problem/POJ-1042
题意：给n个湖，给出每个湖第一次打捞时鱼的数量f[i]，每单位时间鱼减少的数量d[i]，从湖i到湖i+1用时t[i]，在12×h个单位时间内，求最多能获得多少鱼。在获得鱼数量相同的情况下，选择在湖1呆时间最长的方案，若在湖1呆的时间一样，则选呆在湖2时间最长的方案...输出在每个湖呆的时间和最多获得鱼的数量。
思路：最近3天学校开运动会，下周要去西安邀请赛了，所以最近开始通过刷题复习学过的算法。今天状态真的不怎么好，昨晚睡得不好，上午11点多开了这道题，最开始从DP角度想，想好久也没有头绪，看了网上大部分用贪心写的，也有用dp的，今天累，不想研究dp的思路。。。就用贪心来写把。因为各种原因这题写了一下午，各种找bug，心态爆炸，也不知道是因为状态不好还是题目坑QAQ...
好吧，回到题目上来。贪心思路很简单，也很巧妙。枚举最多到达湖i，然后用时间h减去中间行走的时间，剩下的时间就是花在钓鱼上的时间啦。不用考虑行走的时间，这时候由贪心策略，每次找当前能钓到最多鱼的湖去钓，而不一定是后面的湖，这里稍微想一想，不难理解。
再说一下我在写这题时遇到的问题吧QAQ。最开始提交是TLE，我懵逼了。。这数据！这复杂度怎么会T，找好久发现while循环那出现了死循环，因为hh可能<0，这个时候要break。然后就是一直WA，WA了十多发，WA哭。。原因是这组数据：
2
1
0 0
1 1
1
答案是0,但我最终找k时，应该将k初始化为1,再找，不然k是随机的。。累。。
AC代码：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,h; int t[30],f[30],d[30]; int ans1[30][30],ans2[30]; int main(){ while(scanf("%d",&n),n){ for(int i=1;i<=n;++i){ ans2[i]=0; for(int j=1;j<=n;++j) ans1[i][j]=0; } scanf("%d",&h); h*=12; 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-1;++i) scanf("%d",&t[i]); for(int i=1;i<=n;++i){ int nw[30],hh=h; for(int j=1;j<=i;++j){ nw[j]=f[j]; if(j<i) hh-=t[j]; } if(hh<=0) break; while(hh--){ int Max=nw[1],k=1; for(int j=2;j<=i;++j) if(nw[j]>Max){ Max=nw[j]; k=j; } nw[k]-=d[k]; if(nw[k]<0) nw[k]=0; ans2[i]+=Max; ++ans1[i][k]; } } int k=1,Max=ans2[k]; for(int i=2;i<=n;++i) if(ans2[i]>Max) k=i,Max=ans2[i]; for(int i=1;i<=n;++i){ if(i!=1) printf(", "); printf("%d",ans1[k][i]*5); } printf("\n"); printf("Number of fish expected: %d\n\n",ans2[k]); } return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10840010.html