John is going on a fishing trip. He 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.这道题的分析
时间: 2023-06-11 18:08:18 浏览: 157
acm贪心 gone fishing
这道题是一道动态规划问题,需要考虑到以下几个因素:
1. 状态定义:设f(i, j)表示从起点到i时,已经用了j个5分钟的时间,能抓到的最大鱼数。
2. 状态转移:因为从i到j只能走一次,所以可以考虑枚举上一个节点k,转移方程为:f(i, j) = max{f(k, j-ti) + max(0, fi-(j-ti)*di)},其中ti表示从节点k到节点i需要的时间,fi表示节点i初始时能抓到的鱼数,di表示每5分钟减少的鱼数。
3. 边界条件:f(1, 0) = f(1, 5) = ... = f(1, h*12) = f(1, h*12+1) = ... = f(1, h*12+4) = 0,表示从起点出发,初始时不能抓到任何鱼。
4. 最终答案:最终答案为max{f(i, j)},其中i表示所有节点中的任意一个节点,j表示用的时间不超过h小时。
需要注意的是,因为每个节点只能经过一次,所以在状态转移时需要枚举上一个节点k,而不能枚举用了多长时间。而且因为时间只能是5的倍数,所以需要将h换算成12h。
阅读全文