鱼塘钓鱼(fishing）

题目描述

$N$ 个鱼塘排成一排，第 $i$ 个鱼塘第 1 分钟能钓 $f_i$ 条鱼，之后每分钟减少 $d_i$ （减到非正数后无鱼）。从第 $i$ 个鱼塘走到第 $i+1$ 个需 $t_i$ 分钟，只能向右走。总时间 $T$ ，求最多能钓多少鱼。

输入：5 行，依次为 $N$ ； $f_1..f_N$ ； $d_1..d_N$ ； $t_1..t_{N-1}$ ； $T$ 。
输出：一个整数，最多钓到的鱼数。
样例输入/输出：见 problem.md。

思路

枚举最远走到第 $L$ 个塘，路程固定后剩余时间全部用于钓鱼。每个塘每分钟收益递减，把所有已到达鱼塘的每分钟收益展开成一个序列，取前 剩余时间 大的和即为该路线的最优值。

参考代码

Python 版：

python

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
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:42
# update_at: 2026-09-30 07:48

import sys


def bait_catch(rate: list[int], drop: list[int]) -> list[int]:
    """一个鱼塘从下钩到收竿、每一分钟能钓到的鱼数，按递减顺序列出。

    每分钟的收益比上一分钟少 drop，减到非正数就没鱼可钓，所以钓满
    ceil(rate/drop) 分钟即可，得到 rate, rate-drop, ..., rate-(count-1)*drop。
    """
    count = -(-rate // drop)  # ceil(rate/drop)，即这个鱼塘值得钓的分钟数
    return [rate - k * drop for k in range(count)]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    rate = [next(data) for _ in range(n)]              # 各鱼塘第 1 分钟能钓到的鱼数
    drop = [next(data) for _ in range(n)]              # 各鱼塘每钓一分钟的收益衰减量
    walk = [next(data) for _ in range(n - 1)]          # 第 i 个到第 i+1 个鱼塘的路程时间
    deadline = next(data)                              # 截止时间 T

    best = 0
    spent = 0                         # 走到第 last 个鱼塘累计花掉的路程时间
    picks: list[int] = []             # 1..last 号鱼塘全部可用分钟的收益，降序
    for last in range(1, n + 1):
        left = deadline - spent       # 总时间减去路程，其余都能用来钓鱼
        if left < 0:                  # 时间已经耗光，更远的鱼塘只会更亏
            break
        picks += bait_catch(rate[last - 1], drop[last - 1])
        picks.sort(reverse=True)
        best = max(best, sum(picks[:left]))  # 挑收益最高的 left 分钟去钓
        if last < n:
            spent += walk[last - 1]
    print(best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:23
 * update_at: 2026-10-05 12:23
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const int MAXT = 1005;

ll f[MAXN];      // 第 i 个鱼塘第 1 分钟能钓到的鱼数
ll d[MAXN];      // 第 i 个鱼塘每分钟钓鱼数的减少量
ll t[MAXN];      // 从第 i 个鱼塘走到第 i+1 个鱼塘的时间
ll picks[MAXN * MAXT]; // 所有鱼塘展开后的每分钟收益
int pick_cnt;    // picks 当前有效长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    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];
    int T;
    cin >> T;

    ll best = 0;
    ll spent = 0; // 走到当前最远鱼塘累计花费的路程时间
    pick_cnt = 0;

    for (int L = 1; L <= n; ++L) {
        int left = T - spent; // 剩余可用于钓鱼的分钟数
        if (left < 0) break;  // 时间已不够走到更远的鱼塘

        // 把第 L 个鱼塘的每分钟收益展开并加入 picks
        ll cur = f[L];
        while (cur > 0) {
            picks[pick_cnt++] = cur;
            cur -= d[L];
        }

        // 降序排序，取前 left 大求和
        sort(picks, picks + pick_cnt, greater<ll>());
        ll sum = 0;
        int use = min(left, pick_cnt);
        for (int i = 0; i < use; ++i) sum += picks[i];
        if (sum > best) best = sum;

        if (L < n) spent += t[L];
    }

    cout << best << "\n";
    return 0;
}

鱼塘钓鱼(fishing）

目录

题目描述

思路

参考代码