题目描述

在一条水平路边，有 n 个钓鱼湖，从左到右编号为 1∼n。

佳佳有 H 个小时的空余时间，他希望利用这个时间钓到更多的鱼。

他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 5 分钟的倍数）钓鱼。

最后在某一个湖边结束钓鱼。

佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti 分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi 条鱼，以后每再钓 5 分钟，可以钓到的鱼量减少 Di，若减少后的鱼量小于 0，则减少后的鱼量为 0。

为了简化问题，佳佳假定没有其他人钓鱼，也没有其他因素影响他钓到期望数量的鱼。

算法思路

1、钓鱼结束必定以1-n个湖结束，则可以将这n种情况全部枚举，求最大值

2、对于以第t个湖结束的，我们假设钓鱼的时间片段有k个(每个片段5分钟)，假设每个湖都钓k个片段，则共有t*k个

    记录，我们用三元组（f, i, j)存取该记录，三元组表示第i个湖在该湖上第j个时间片段钓了f条鱼

3、将t*k个三元组排序，选取f最大的k个，相加就是一次结果。（因为对于每个湖来说，随着时间的增加，我们钓的

    鱼数量f是随着时间j增加而减少的，所有当我们对这t*k个三元组按照f排序的时候，对于同一个湖i，其j小的一定会被

    j大的优先选到，则我们选到的k个三元组，可以根据i值分成t波，每一波都是从j=1递增选取的，最后产生的序列

    即为本次结果如何选取的序列）

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node{
    int fish, i, j;

    bool operator < (const node & x) const{
        if(fish < x.fish) return true;
        return false;
    }
};//三元组，表示第i个湖在第j个时间片段钓鱼数量

int main()
{
    int n, h;

    cin >> n >> h;

    int f[n + 1], d[n + 1], ti[n + 1];//分别湖的起始鱼的数量，递减数量，两个湖的距离

    for (int i = 1; i <= n; i ++) cin >> f[i];
    for (int i = 1; i <= n; i ++) cin >> d[i];
    ti[1] = 0;//第1个湖没有距离
    for (int i = 2; i <= n; i ++) cin >> ti[i];

    int ans = 0, walktime = 0;

    for (int i = 1; i <= n; i ++)
    {
        walktime += ti[i];
        int k = h * 12 - walktime;//以i个湖结束剩余可支配的时间片段

        if(k < 0) break;
        vector<node> F;
        for (int p = 1; p <= i; p ++)
        {
            for (int t = 1; t <= k; t ++)
            {
                int num = f[p] - (t - 1) * d[p];
                if(num > 0) F.push_back({num, p, t});
                else F.push_back({0, p, t});
            }
        }//前i - 1个湖每个湖递减产生k个三元组，fish小于0就将fish置于0
        sort(F.begin(), F.end());
        int res = 0;
        while(k --)
        {
            res += F.back().fish;
            F.pop_back();
        }//取最大的前k个三元组记录

        if(ans < res)
            ans = res;
    }
    cout << ans << endl;

}