鱼塘钓鱼（多路归并）

有 $N$ 个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：$N=5$ 时，如下表：

鱼塘编号	1	2	3	4	5
第1分钟能钓到的鱼的数量（1..1000）	10	14	20	16	9
每钓鱼1分钟钓鱼数的减少量（1..100)	2	4	6	5	3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）	3	5	4	4

即：在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼，第 2 分钟内只能钓到 8 条鱼，……，第 5 分钟以后再也钓不到鱼了。

从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟，从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟，……

给出一个截止时间 T，设计一个钓鱼方案，从第 1 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

数据范围

$1≤N≤100$ ,
$1≤T≤1000$

思路：

首先明确一点，从某一鱼塘中每分钟能钓上的鱼数只有在到达该鱼塘后才会开始减少。

对样例进行分析可以发现，每个鱼塘每分钟能钓上鱼的数量是等差数列。

能用于钓鱼的总时间：$T_{钓鱼} = T_{总} - (T_{1}+\cdots +T_{i})$

其中：全部时间 $T_{总}$，走到鱼塘 $i$ 花费的总时间$T_{1}+\cdots+T_{i}$。

由于每次都是从$1$号鱼塘出发，因此可以枚举每次最终到达的鱼塘编号$i$， 并求此时的最大钓鱼数。

由于时间间隔都是$1$分钟，接下来的工作就是在等差数列$1$到等差数列$i$的所有数值中，选取前$T_{钓鱼}$个值。这显然是一个多路归并问题。

代码：

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

const int N = 110;
int f[N], d[N], t[N], spend[N];

int get(int i)
{
    return max(0, f[i] - d[i] * spend[i]);//返回当前鱼塘i的每分钟钓鱼数，该值非负
}

int check(int n, int T)
{
    int res = 0;
    memset(spend, 0, sizeof(spend));//spend数组用于记录1~i号鱼塘各自当前已经使用的时间
    while(T--)
    {
        int j = -1;
        //由于数据范围很小，因此每次直接暴力枚举，寻找所有等差数列中剩余数中的最大值
        for(int i = 1; i <= n; ++i)
            if(j == -1 || get(i) > get(j))
                j = i;
        res += get(j), ++spend[j];
    }
    return res;
}

int main()
{
    int n, T, res = 0;
    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)
    //由于总是从鱼塘1出发，因此求时间前缀和，即若要能够从第1~i个鱼塘中钓鱼，需要花费在走路上的时间
        cin >> t[i], t[i] += t[i - 1];
    cin >> T;
    for(int i = 1; i <= n; ++i)//枚举终点鱼塘
        res = max(res, check(i, max(0, T - t[i - 1])));
    cout << res << endl;
    return 0;
}