鱼塘钓鱼_(贪心，多路归并）

原图链接：1262. 鱼塘钓鱼 - AcWing题库

题意：给定鱼塘间距离，每个鱼塘每分钟能钓到多少鱼（递减），要求规划一个方案使得在规定时间内调到的鱼最多

思路

两步贪心

首先明确不可能往回走，即去到另一鱼塘后不可能返回——基于贪心，如果返回了，那就说明可以再在那个鱼塘继续钓鱼的时候出发去到其他鱼塘，导致为了最佳的钓鱼数量又回来。相比在一个鱼塘花费最佳时间再去到下一个鱼塘，前者肯定劣于后者。

第二步贪心

其实是分类： 我一直考虑到是过程化的，即什么时候走最佳，以这个思路展开，发现不知道怎么做

实际上应该看得更抽象一些，枚举明确要去多少个鱼塘，就不必考虑具体要在什么时候走，什么时候走了优于留下钓鱼，而是枚举要去哪个鱼塘，去多少个后对这些鱼塘的钓鱼数合并排序找最优即可，而不必考虑具体的细节。

前提是：鱼塘中每分钟鱼数递减（与钓鱼次数相关）

多路归并是一种思想，指的是将不同数组合并为一个数组考虑，可能涉及排序等内容

实现

//枚举所有可能路径
//取最大值
 
#include <iostream>
#include <algorithm>
#include <vector>
//#include <queue>
 
using namespace std;
 
const int N = 1010, M = 100 * N;
 
//priority_queue<int> q;
int d[N];
int h[N];
int sub[N];
vector<int> fish;
 
int main()
{
    int n, L;
    cin >> n;
    
    for(int i = 0; i < n; i ++)
        cin >> h[i];
     
    for(int i = 0; i < n; i ++)
    {
        cin >> sub[i];
        
    }
    
        
    for(int i = 1; i < n; i ++)
    {
        cin >> d[i];
        d[i] += d[i-1];
    }
    
    cin >> L;
    
    int ans = 0;
    for(int i = 0; i < n; i ++)
    {
    //遍历的时候归并，排序
        int t = h[i];
        while(t > 0) 
        {
            fish.push_back(t);
            t -= sub[i];
        }
        fish.push_back(0);
        
        sort(fish.begin(), fish.end(), greater<int>());
        
        t = L - d[i];
        int sum = 0;
        for(long long i = 0; i < t && i < fish.size();  i ++)
        {
            sum += fish[i];
        }
        
        ans = max(ans, sum);
    }
    
    cout << ans << endl;
    
    return 0;
}