Gone Fishing

悠悠 2023-01-09 14:11 111阅读 0赞

## Gone Fishing ##

John is going on a fishing trip. H  
e has h hours available (1 <= h <= 16), and there are n lakes in the area (2 <= n <= 25) all reachable along a single, one-way road. John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,…,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 < ti <=192). For example, t3 = 4 means that it takes 20 minutes to travel from lake 3 to lake 4. To help plan his fishing trip, John has gathered some information about the lakes. For each lake i, the number of fish expected to be caught in the initial 5 minutes, denoted fi( fi >= 0 ), is known. Each 5 minutes of fishing decreases the number of fish expected to be caught in the next 5-minute interval by a constant rate of di (di >= 0). If the number of fish expected to be caught in an interval is less than or equal to di , there will be no more fish left in the lake in the next interval. To simplify the planning, John assumes that no one else will be fishing at the lakes to affect the number of fish he expects to catch.  
Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be a multiple of 5.  
**Input**  
You will be given a number of cases in the input. Each case starts with a line containing n. This is followed by a line containing h. Next, there is a line of n integers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), and finally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in which n = 0.  
**Output**  
For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to be caught (you should print the entire plan on one line even if it exceeds 80 characters). This is followed by a line containing the number of fish expected.  
If multiple plans exist, choose the one that spends as long as possible at lake 1, even if no fish are expected to be caught in some intervals. If there is still a tie, choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.  
**Sample Input**

2 
    1 
    10 1 
    2 5 
    2 
    4 
    4 
    10 15 20 17 
    0 3 4 3 
    1 2 3 
    4 
    4 
    10 15 50 30 
    0 3 4 3 
    1 2 3 
    0

**Sample Output**

45, 5 
    Number of fish expected: 31 
    
    240, 0, 0, 0 
    Number of fish expected: 480 
    
    115, 10, 50, 35 
    Number of fish expected: 724

这道题的中文意思就是：  
**有n(2<=n<=25)个湖从左到右一字排开。从第i个湖走到第i+1个湖要耗时t\[i\]个时间片（每个时间片5分钟）。  
John有h(1<=h<=16)个小时可以用在这些湖钓鱼（包括湖间行走时间）。在每个湖待的时间必须是整数个时间片或0。就算钓不着鱼了，也可以在湖边呆着。  
对于湖i，John在那里的第一个时间片可以钓到鱼f\[i\]条，且后续的每个时间片，能钓到的鱼数量都比上一个时间片少d\[i\]。  
注意John只能从第一个湖出发，从左往右走，不能回头。最后John要停在哪里都可以。问John最多能钓多少条鱼。**  
*输入：  
每个测试用例，首先给出池塘数n，然后是时间h(小时为单位),接下来的两行分别有n个整数，分别表示f\[i\]和d\[i\],接下来的一行为n-1个整数，表示t\[i\]。n为0时表示输入结束。  
输出：  
对于每个测试用例，第一行依次输出在每个池塘的停留时间(分钟为单位)，每个时间之间用逗号+空格分开。第二行输出能钓到的最多的鱼的数量*

本题采用的是贪心算法，后面的代码是参照他人的：

#include<stdio.h>
    int fi[30];
    int di[30];
    int ti[30];
    int cfi[30];
    int h,n;
    struct st
    { 
    	int max;
    	int num[30];
    }lake[30];
    int getmax(int p[],int i,int j)//找出能钓最多鱼的湖
    { 
    	int l=i,max=p[i];
    	for(int m=i+1;m<=j;m++)
    	{ 
    		if(max<p[m])
    		{ 
    			max=p[m];
    			l=m;
    		}
    	}
    	return l;
    }
    void getfish()
    { 
    	int i;
    	for(i=1;i<=n;i++) //初始化
    	{ 
    		lake[i].max=0;
    		for(int j=1;j<=n;j++)
    		{ 
    			lake[i].num[j]=0;
    		}
    	}
    	for(i=1;i<=n;i++)//i表示结束钓鱼时的湖序号 
    	{ 
    		int t=0;
    		int T=h*60;
    		for(int j=1;j<=i;j++)
    		{ 
    			cfi[j]=fi[j];
    			if(j<i)
    			T=T-ti[j]*5;
    		}
    		while(t<T)
    		{ 
    			int k=getmax(cfi,1,i);//找到当前情况下，钓鱼量最大的湖进行钓鱼 
    			lake[i].num[k]+=5;
    			lake[i].max+=cfi[k];
    			cfi[k]=(cfi[k]>di[k])?cfi[k]-di[k]:0;
    			t+=5;
    		}
    	}
    	for(i=1;i<=n;i++)//找出钓鱼量最多下标，即为结束钓鱼的湖序号 
    	{ 
    		cfi[i]=lake[i].max;
    	}
    	int l=getmax(cfi,1,n);
    	for(i=1;i<=n;i++)
    	{ 
    		if(i!=n){ 
    			printf("%d, ",lake[l].num[i]);
    			int a=lake[l].num[i];
    		}
    		else{ 
    			printf("%d\n",lake[l].num[i]); 
    			int b=lake[l].num[i];
    		}
    	}
    	printf("Number of fish expected: %d\n\n",lake[l].max);
    }
    int main()
    { 
    	int i;
    	while(scanf("%d",&n),n)
    	{ 
    		scanf("%d",&h);
    		for(i=1;i<=n;i++)
    		{ 
    			scanf("%d",&fi[i]);
    		}
    		for(i=1;i<=n;i++)
    		{ 
    			scanf("%d",&di[i]);
    		}
    		for(i=1;i<n;i++)
    		{ 
    			scanf("%d",&ti[i]);
    		}
    		getfish(); 
    	}
    	return 0;
    }

附上该程序的debug视频，帮助理解整个运行过程：  
[https://www.bilibili.com/video/BV1JU4y1s7Tv][https_www.bilibili.com_video_BV1JU4y1s7Tv]

[https_www.bilibili.com_video_BV1JU4y1s7Tv]: https://www.bilibili.com/video/BV1JU4y1s7Tv