钓鱼问题

题目描述

某人想在 hh 小时内钓到数量最多的鱼。这时他已经在一条路边,从他所在的地方开始,放眼望去,nn 个湖一字排开,湖编号依次是 1.2…n1.2\dots n。他已经知道,从湖 ii 走到湖 i+1i+1 需要花 5∗ti5*t_i 分钟;他在湖 ii 钓鱼,第一个 55 分钟可钓到数量为 fif_i 的鱼,若他继续在湖 ii 钓鱼,每过 55 分钟,钓鱼量将减少 did_i

请给他设计一个最佳钓鱼方案

(1<=H<=6,2<=n<=25)(1<=H<=6,2<=n<=25)

输入格式

第一行:湖的数量 nn

第二行:时间 hh(小时)。

第三行:nn 个数, f1,f2,…fnf_1,f_2,\dots f_n

第四行:nn 个数, d1,d2,…dnd_1,d_2,\dots d_n

第五行:n−1n-1 个数, t1,t2,…tn−1t_1,t_2,\dots t_{n-1}​

输出格式

一个数,表示所能钓鱼的最大数量

输入输出样例

输入

1
2
3
4
5
2
1
10  1
2  5
2

输出

1
31

方法 1:贪心+枚举

思路分析

大致的思路如下

应用贪心的策略,可以得到钓鱼佬只能向前走,返回的话只会增加钓鱼佬在路上的时间,不符合贪心的局部最优策略

接下来可以进行分析,可以得到赶路的时间其实是确定的,因为不存在回头路,所以我们不妨假设这是个超级钓鱼佬,可以在需要的时候瞬移到某个钓鱼量最大的湖里,则我们需要实时找出当前钓鱼量最大的湖

每次选择哪个湖的顺序对钓鱼佬的最优钓鱼策略是不影响的,符合局部最优特性,我们认为每一个湖都有可能作为最终状态,所以需要从第一个湖开始遍历所有 n 个湖,来寻求这 n 个湖作为结束湖时的最大钓鱼数量,这部分可以根据贪心策略得到局部最优钓鱼策略

但如果单纯的使用贪心策略有个问题:到底该在哪个湖停下来钓到最后(无法确定终态),故我们需要先使用贪心策略计算出每一个湖作为终态的局部最优解,然后再使用枚举的方法来计算出最终的最优解,从而得到全局最优解

则最终算法流程如下:

  1. 枚举钓鱼佬经过的最后一个湖,每种情况减去所需步行的时间,剩下的就是钓鱼的时间

  2. 每 5 分钟选取钓鱼量最多的湖进行钓鱼,直到时间耗尽

  3. 在所有枚举的情况中选择钓鱼量最多的情况,即为问题的最优解

编码实现

变量定义

n,h,f[],d[],t[]用于存储上述输入的数据,tmp[]数组用于存储过程中产生的临时数据

另定义一个结构体数组Lake[]用于存储状态,Lake[i]表示经过最后一个湖i时,当前的状态

结构体成员说明如下:

  • 成员num[i]表示当前状态下,各个湖的钓鱼时间

  • 成员max表示当前状态下,最大的钓鱼数量

1
2
3
4
5
6
7
8
#define MAX 30
int n, h, ansPoint = 1;
int f[MAX], d[MAX], t[MAX], tmp[MAX];
struct NodeType
{
    int num[MAX];
    int max;
} Lake[MAX];

数据输入

声明数据结构完毕,开始处理输入数据,将输入数据存入上述变量与数组中,并对Lake[]进行初始化,将其全部数据位初始化为0

1
2
3
4
5
cin >> n >> h;
for (int i = 1; i <= n; i++)cin >> f[i];
for (int i = 1; i <= n; i++)cin >> d[i];
for (int i = 1; i < n; i++)cin >> t[i];
memset(Lake, 0, sizeof(Lake));

核心处理函数

接下来进入核心处理流程,先给出处理函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    int restT, fishingTime;
    for (int i = 1; i <= n; i++)
    {
        restT = h * 60, fishingTime = 0;
        for (int j = 1; j < i; j++) restT -= 5 * t[j];
        memcpy(tmp, f, sizeof(f));
        while (fishingTime < restT)
        {
            int k = max_element(tmp + 1, tmp + i + 1) - tmp;
            if (tmp[k] == 0) break;
            Lake[i].max += tmp[k];
            Lake[i].num[k] += 5, fishingTime += 5;
            tmp[k] >= d[k] ? tmp[k] -= d[k] : tmp[k] = 0;
    }
}

首先枚举每一个可能的结束湖位置,需要一个局部变量restT,用于存储从第一个湖到当前这个湖赶路花费了多少时间

由于钓鱼佬只能向前走,返回的话只会增加钓鱼佬在路上的时间,不符合贪心的局部最优策略,故若以第 n 个湖作为终态,则只需要考虑前 n-1 个湖的赶路时间即可

1
2
3
restT = h * 60;
for (int j = 1; j < i; j++)
    restT -= 5 * t[j];

其次是需要针对f[]制作一份拷贝用于后续的处理,避免对原始数据修改造成影响,直接使用memcpy拷贝整个数组

1
memcpy(tmp, f, sizeof(f));

接下来的流程需要分析若第 i 个湖为终态(即最终在这个湖结束处理),对于前 n-1 个湖采用的贪心策略fishTime用于存储,遍历完毕剩下的时间,结束的标志是剩余时间小于等于 0

1
2
3
4
5
6
fishingTime = 0;
while (fishingTime < restT)
{
    //循环体部分,见下文
    fishingTime += 5;
}

接下来分析循环体内部流程

首先找到当前时刻能提供最大钓鱼量的湖泊的下标,并将其赋值给k

1
int k = max_element(tmp + 1, tmp + i + 1) - tmp;

当然,如果当前这个最大值已经是0了,则表示所有的湖里都被钓绝种了,则直接跳出循环

1
if (tmp[k] == 0) break;

接下来是一套连击

  • 首先将当前湖泊的钓鱼量加上当前时刻的钓鱼量,并将其赋值给Lake[i].max,标记了贪心算法的局部最优解

  • 其次更新当前状态,令状态数组内储存的状态获得更新,令第k个湖泊钓鱼时长增加5

  • 最后,更新湖中出现的鱼数量,注意在某个湖中的钓鱼数在维护后可能会出现负数,此时应将该湖中每个时间单位的钓鱼数更新为零

1
2
3
Lake[i].max += tmp[k];
Lake[i].num[k] += 5;
tmp[k] >= d[k] ? tmp[k] -= d[k] : tmp[k] = 0;

收尾工作

找出状态数组内局部最优解最大的那一组的下标,获取ansPoint

1
2
for (int i = 2; i <= n; i++)
    ansPoint = Lake[i].max > Lake[ansPoint].max ? i : ansPoint;

输出结果

1
2
3
for (int i = 1; i <= n; i++)
    printf("在湖 %d 钓鱼时间为 %d 分钟\n", i, Lake[ansPoint].num[i]);
cout << Lake[ansPoint].max << endl;

整体代码(带注释)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define MAX 30
int n, h, ansPoint = 1;
int f[MAX], d[MAX], t[MAX], tmp[MAX];
struct NodeType
{
    int num[MAX]; //各个湖的钓鱼时间
    int max;      //最多的钓鱼量
} Lake[MAX];      // Lake[i]表示经过最后一个湖i的结果
//求解钓鱼问题
void solve()
{
    int restT, fishingTime;
    for (int i = 1; i <= n; i++) //枚举每一个可能的结束湖位置
    {
        restT = h * 60, fishingTime = 0; //剩下的时间
        for (int j = 1; j < i; j++) restT -= 5 * t[j];
        memcpy(tmp, f, sizeof(f));
        while (fishingTime < restT) //考虑所有的钓鱼时间
        {
            int k = max_element(tmp + 1, tmp + i + 1) - tmp; //找到钓鱼量最多的湖k
            if (tmp[k] == 0) break; //如果没有钓鱼量了，则退出循环
            Lake[i].max += tmp[k];                        //在湖k中钓一个时间单位的鱼
            Lake[i].num[k] += 5, fishingTime += 5;        //湖i的钓鱼时间增加一个单位时间,总时间增加一个单位时间
            tmp[k] >= d[k] ? tmp[k] -= d[k] : tmp[k] = 0; //修改湖k下一个单位时间的钓鱼量,若余量不足，则设为0
        }
    }
}
int main()
{
    cin >> n >> h;
    for (int i = 1; i <= n; i++) cin >> f[i];
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i < n; i++) cin >> t[i];
    memset(Lake, 0, sizeof(Lake)); // lake数组初始化
    solve();
    for (int i = 2; i <= n; i++)
        ansPoint = Lake[i].max > Lake[ansPoint].max ? i : ansPoint;
    for (int i = 1; i <= n; i++)
        printf("在湖 %d 钓鱼时间为 %d 分钟\n", i, Lake[ansPoint].num[i]);
    cout << Lake[ansPoint].max << endl;
}

方法 2:动态规划

动态规划的核心思路是需要找到状态转移方程

我们以 5 分钟为一个单位时间,定义一个数组 opt

opt[i][j],用于表示:走到第 i 个湖花 j 个单位时间可以钓到的最多鱼数量

我们设在湖 i 花了 k 个单位时间钓鱼,从湖 i-1 走到湖 i 要花 t[i-1] 的时间

那么 opt[i][j] 就等于 opt[i][j-t[i-1]-k]加上在湖 i 花 k 个单位时间钓到的鱼

opt[i][j-t[i-1]-k]即从opt[i][j]这个湖到上一个湖花费 {j−(i−t)−k}\{j-(i-t)-k\} 个单位时间的最优解(tt为第11个湖到第ii个湖移动耗时)

那么很明显的可以看见从 i 到 i-1 的状态转移,根据这个规律可以构建转移方程

opt[i][j]=max⁡{opt[i−1][j−t[i−1]−k]+(k∗f[i])−(d[i]+2∗d[i]+3∗d[i]+⋯+(k−1)∗d[i])}opt[i][j]=\max\{opt[i-1][j-t[i-1]-k]+ (k*f[i])-(d[i]+2*d[i]+3*d[i]+\dots+(k-1)*d[i])\}

由等差数列求和公式,可化简得到

opt[i][j]=max⁡{opt[i−1][j−t[i−1]−k]+(k∗f[i])−(k∗(k−1)2∗d[i])}opt[i][j] = \max\{opt[i-1][j-t[i-1]-k] + (k*f[i]) - (\frac{k*(k-1)}{2}*d[i])\}

那么状态转移已经构建完成了,我们只需要求出最优解即可,现在就要来看 k 的取值范围

很容易就可以知道,数组下标不能为负,所以 k 必须满足k<=j-t[i-1],由于钓的鱼的数量为正,所以有 (k-1)*d[i]<f[i]

还有一点最重要,就是因为到除湖 1 之外的湖都需要时间,所以 opt[i][0](i>1)(i>1) 是无意义的

所以当 k 要保证 opt[i][j-t[i-1]-k] 有意义,我们需要在一开始初始化的时候把 opt 都赋值成 INT_MIN ,表示无意义,通过只把 opt[0][0] 赋初值为 0,用于保证 opt[1][*] 有意义,从而保证其他的有意义

#define INT_MIN (-__INT_MAX__ -1)

__INT_MAX__ = 2147483647

则该值为 -2147483648

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define DEBUG
using namespace std;
int opt[30][10000], f[30], d[30], t[30], n, h, ans = INT_MIN;
int main()
{
    cin >> n >> h;
    for (int i = 1; i <= n; ++i) cin >> f[i];
    for (int i = 1; i <= n; ++i) cin >> d[i];
    for (int i = 1; i < n; ++i) cin >> t[i];
    memset(opt, INT_MIN, sizeof(opt));
    opt[0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= h * 12; ++j)
        {
            for (int k = 0; k <= j - t[i - 1]; ++k)
                if ((k - 1) * d[i] < f[i] && opt[i - 1][j - t[i - 1] - k] != INT_MIN)
                {
                    opt[i][j] = max(opt[i][j], opt[i - 1][j - t[i - 1] - k] + k * f[i] - k * (k - 1) / 2 * d[i]);
                    ans = max(ans, opt[i][j]);
                }
        }
    cout << ans << endl;
    return 0;
}