@TOC


💐The Begin💐点点关注,收藏不迷路💐

在一条水平路边,有 n(2≤n≤100)个钓鱼湖,从左到右编号为 1,2,…,n。佳佳有 H(1≤H≤20)个小时的空余时间,他希望利用这个时间钓到更多的鱼。他从 1号出发,向右走,有选择的在一些湖边停留一定的时间(是 5 分钟的倍数)钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 ii个湖到第 i+1个湖需要走 5×Ti分钟路,还测出在第 i 个湖停留,第一个 5 分钟可以钓到Fi条鱼,以后每再钓 5分钟,可以钓到的鱼量减少 Di,若减少后的鱼量小于 000,则减少后的鱼量为 000 。为了简化问题,佳佳假定没有其他人钓鱼,也没有其他因素影响他钓到期望数量的鱼。请编程求出佳佳最多能钓鱼的数量。

输入

第一行一个整数 n,表示湖的个数

第二行一个整数 H,表示佳佳的空闲时间

第三行有 n个整数,依次表示每个湖第一个 5分钟能钓到鱼的数量

第四行有 n个整数,依次表示以后的每5分钟钓鱼数量比前一个 5 分钟钓鱼数量减少的数量

第五行有 n−1 个整数,Ti 表示由第 i 个湖到第 i+1个湖需要花 5×Ti分钟的路程

输出

输出只有一行,表示佳佳最多能钓鱼的数量。

样例输入

3
1
4 5 6
1 2 1
1 2

样例输出

35

提示
数据提示 对于 100%的数据,2≤n≤100,1≤H≤20。

#include <iostream>
#include <algorithm>
using namespace std;

// 用于快速读取输入数据,避免频繁调用输入输出流导致效率稍低的情况
inline int read() {
    char c = getchar();
    int num = 0, sign = 1;
    while (c < ‘0’ || c > ‘9’) {
        if (c == ‘-’) sign = -1;
        c = getchar();
    }
    while (c >= ‘0’ && c <= ‘9’) {
        num = num * 10 + (c - ‘0’);
        c = getchar();
    }
    return num * sign;
}

int main() {
    int n; // 湖的数量
    int h; // 空闲小时数,换算成以5分钟为单位
    n = read();
    h = read();
    h *= 12; // 1小时等于12个5分钟,进行单位换算

    int fishFirst[110]; // 存储每个湖第一个5分钟钓到鱼的数量
    int fishDecrease[110]; // 存储每个湖每5分钟鱼量减少的值
    int timeToNext[100]; // 存储相邻湖之间走路花费的5分钟的个数(因为最后一个湖不需要到下一个湖的时间,所以长度为n - 1即可)

    // 读取每个湖第一个5分钟钓到鱼的数量
    for (int i = 1; i <= n; i++) {
        fishFirst[i] = read();
    }
    // 读取每个湖每5分钟鱼量减少的值
    for (int i = 1; i <= n; i++) {
        fishDecrease[i] = read();
    }
    // 读取相邻湖之间走路花费的5分钟的个数,并计算累计路程时间(以5分钟为单位)
    for (int i = 1; i < n; i++) {
        int temp = read();
        timeToNext[i] = (i == 1)? temp : timeToNext[i - 1] + temp;
    }

    int maxFish = 0; // 记录最多能钓到鱼的数量
    for (int farthestLake = 1; farthestLake <= n; farthestLake++) { // 枚举最远到达的湖
        int currentFish[110]; // 用于记录当前可钓鱼的湖在每个时刻能钓到鱼的数量,每次循环初始化
        for (int i = 1; i <= farthestLake; i++) {
            currentFish[i] = fishFirst[i]; // 初始化为每个湖第一个5分钟钓到鱼的数量
        }

        int remainingTime = h - timeToNext[farthestLake - 1]; // 计算剩余可钓鱼时间(以5分钟为单位)
        int currentSum = 0; // 当前从起始湖到最远到达湖能钓到鱼的总数,每次循环初始化

        while (remainingTime > 0 && currentSum >= 0) { // 只要还有剩余时间且当前钓到鱼的总数非负(防止出现异常情况导致无限循环)
            int maxFishThisTime = 0; // 当前5分钟内能钓到鱼的最大数量
            int lakeIndex = 0; // 对应鱼量最多的湖的索引

            // 寻找当前能钓到鱼最多的湖
            for (int i = 1; i <= farthestLake; i++) {
                if (currentFish[i] > maxFishThisTime) {
                    maxFishThisTime = currentFish[i];
                    lakeIndex = i;
                }
            }

            if (maxFishThisTime == 0) { // 如果当前没有湖能钓到鱼了,结束循环
                break;
            }

            currentSum += maxFishThisTime; // 将当前能钓到的最多鱼量累加到总数中
            currentFish[lakeIndex] -= fishDecrease[lakeIndex]; // 更新钓到鱼的湖的下一个5分钟鱼量
            if (currentFish[lakeIndex] < 0) { // 确保鱼量不小于0
                currentFish[lakeIndex] = 0;
            }

            remainingTime–; // 时间减少一个5分钟单位
        }

        maxFish = max(maxFish, currentSum); // 更新最多能钓到鱼的数量
    }

    cout << maxFish << endl; // 输出最多能钓到鱼的数量

    return 0;
}

在这里插入图片描述


💐The End💐点点关注,收藏不迷路💐
Logo

科技之力与好奇之心,共建有温度的智能世界

更多推荐