poj1042
题目大意：
有n个湖，一个人在这些湖中钓鱼，5分钟钓一次，求给定的时间内能够钓的鱼的最大数量,他的起点是第一个湖泊，可以在任意湖泊终止
但是只能够往下走，不能返回,每次钓到的鱼会在上一次的基础上减少,当所有的湖泊里的鱼能够钓的数量为0时，但是时间还有剩，都算到第
一个湖泊上
输出在每一个湖泊呆的时间，及最大钓鱼数量
思路：
枚举+贪心
一一枚举所经过的湖泊，算出该情况的最优解，具体看代码
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int N = 30;//湖的最大数目 const int M = 200;//钓鱼的最大次数,题目所给16小时，5分钟一单位,16*12 //time[i]代表在第i个湖钓鱼的次数,fish[i][j]在第i个湖第j次钓鱼的数量 int time[N],fish[N][M]; int movetime[N];//movetime[1]=0,movetime[i]代表从第i-1个湖移动到第i个湖所需时间 int d[N];//每隔一次钓鱼当再一次钓鱼时减少的数量 int n,h; int main() { //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF&&n) { int ans = 0; memset(time,0,sizeof(time)); memset(movetime,0,sizeof(movetime)); memset(fish,0,sizeof(fish)); scanf("%d",&h); for(int i=1;i<=n;i++) scanf("%d",&fish[i][1]); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=2;i<=n;i++) scanf("%d",&movetime[i]); int totalTime = h*12; time[1]=totalTime;//全0的情况，也就是不会钓到鱼,把所有的时间都花在第一个湖 //初始化每个湖每次钓鱼的数量 for(int i=1;i<=n;i++) for(int j=2;j<=totalTime;j++) fish[i][j]=max(fish[i][j-1]-d[i],0);//不可能是负数 //枚举所有情况，即只在一个湖，两个湖.....n个湖能够钓到最多的鱼 for(int k=1;k<=n;k++) { int maxFish = 0; //计算能够钓鱼的时间,就是减掉移动的时间 int realTime=totalTime; for(int i=2;i<=k;i++) realTime-=movetime[i]; if(realTime<=0) break;//总时间不够耗在路程上时，跳出 //用来临时记录每个湖的钓鱼次数 int temp[N];memset(temp,0,sizeof(temp)); for(int tt=1;tt<=realTime;tt++) { //找出每次钓鱼能够最多数量的湖 //如果所有的湖的鱼都是0的话，那么就把时间加在第一个湖,p=1; int maxs = 0 , p=1; for(int i=1;i<=k;i++) if(fish[i][temp[i]+1]>maxs) { maxs = fish[i][temp[i]+1]; p=i; } maxFish+=maxs; temp[p]++; } //更新最大值情况 if(maxFish>ans) { ans=maxFish; memcpy(time,temp,sizeof(temp)); } } printf("%d",time[1]*5); for(int i=2;i<=n;i++) printf(", %d",time[i]*5); printf(" Number of fish expected: %d ",ans); } }