这道题第一感觉上就是一道完全背包变形，第一次也确实是用dp过了，但是看着标签的队列和贪心，我陷入了沉思......完全不知道怎么用队列和贪心来做，在网上看了各种题解后终于理解了贪心的做法，但是有一说一，这道题dp确实比贪心好理解（然而贪心解法更优）。

更新一下： 咳，第二天再看下面的题解，我自己都不知道自己在说什么了，于是在这里更加直观清晰的梳理一下思路，建议先看这个，在自己理解之后再去看后面的，如果连后面的都可以看懂，那么恭喜你，你已经完全掌握这道题的贪心思路了呢（大雾）。

清晰而直观的思路：

1.拆分贪心局部最优解：找到此刻5分钟内能够钓起最多的鱼的湖，将鱼量加入sum中，然后记得减去递减的鱼量。

2.推导全局最优解： 由于每次局部处理最后都会减去递减的鱼量，所以下一次局部处理中，5分钟内能够钓起最多的鱼的湖可能会改变，故而需要重新遍历所有湖找到此刻鱼量最多的湖，然后进行上述处理。以此类推，直到所有湖的鱼都钓完了，即某时刻每个湖中的鱼量都为0，或者钓鱼的时间消耗完了，处理结束，输出最大的sum即可。

3.问题难点——路程时间的处理： 有人肯定会想，如果按照上述的操作处理，那么，我们假设一种情况，共有3个湖，最优的解法是先在3号湖钓5分钟，然后在1号湖钓5分钟，接着在2号湖钓5分钟，最后再在3号湖钓5分钟，这样岂不是会出现反复横跳，3—>1—>2—>3在路程上花费大量时间的情况？这个路程时间怎么最优呢？

​ 就以这个情况为例吧，最后我们得出的最优解是：在1号湖钓5分钟，在2号湖钓5分钟，在3号湖钓10分钟，已知到达的最远的湖是3号湖，那么就一定会经过1和2号湖，由于我们已经理论计算出最优解，故而我们可以在经过1号湖的时候安排钓5分钟，然后去2号湖钓5分钟，最后再去3号湖钓10分钟，只用走一遍路程不用回头。假设最远湖是x号湖，所以我们可以转换为：钓鱼时间 = 总时间 - 从1号湖走到x号湖的时间，从而做到了路程时间最优。

​ 但是得注意一下，这个只是举例帮助理解的，实际做题中我们并不知道最优解中最远会到达哪个湖，不过这个好解决，就是加个循环遍历一下，让1号湖到n号湖都当一次最远湖，每个都贪心处理一次，然后找到其中sum最大的，就是最优解了。

===================================================================

思路： 很明显这道题的时间是以每5分钟为一单位的，无论是钓鱼，还是鱼的数量递减，都是每5分钟发生一次，所以就把每5分钟作为一单位来处理。于是乎，共有h个单位的钓鱼时间，第一次就可以横向比较每个湖的第1个单位谁钓的鱼最多，记录下是第几个湖，然后由于在这个湖钓了5分钟的鱼，下个5分钟的鱼量会减少，于是跟新这个湖第2单位的鱼量，再拿去和其他湖的第一单位的鱼量比较，找到最大然后进行相同的处理，直到h单位的时间用完或者最大的鱼量为0了也就是说鱼都钓完了，停止循环。那么现在的问题是还有个路程时间怎么处理，是否会有回头客等让人头大的情况？可以转化一下，处理为从第一个湖到第i个湖的时间，假设到达的最远的湖就是第i个湖，这样钓鱼时间h就为总时间减去从第一个湖到第i个湖的时间。从1到n遍历一下最远的湖，每次都贪心找到最大鱼量，最后再比较一下就行了。

#include <bits/stdc++.h>
using namespace std;
int fish[1000], Less[1000], cost[1000]; 
int a[1000];//用于复原fish数组

int main() {
	int n, h, h1, x;
	cin >> n >> h;
	h *= 12;//一小时有12个5分钟
	h1 = h;//用于复原h
	for (int i = 1; i <= n; i++) {
		cin >> fish[i];
		a[i] = fish[i];
	}
	for (int i = 1; i <= n; i++) cin >> Less[i];
	cost[1] = 0;//第一个湖到第一个湖的距离为0
	for (int i = 2; i <= n; i++) {
		cin >> x;
		cost[i] += cost[i - 1] + x;
	}
	int Max = 1, sum = 0, ans = 0;
	for (int i = 1; i <= n; i++) {//遍历走到的最远的湖
		h = h - cost[i];//用于钓鱼的时间
		while (h > 0) {
			for (int j = 1; j <= i; j++) {
				if (fish[Max] < fish[j]) Max = j;	
			}
			if (fish[Max] == 0) break;//鱼都钓完了，退出循环
			sum += fish[Max];
			fish[Max] -= Less[Max];//钓完5分钟，鱼递减
			if (fish[Max] < 0) fish[Max] = 0;
			h--;
		}
		ans = max(ans, sum);//记录最大值
		sum = 0;// 每次最远的湖改变都要重新贪心处理一次，所以复原数据
		h = h1;
		for (int i = 1; i <= n; i++) fish[i] = a[i];
	}
	cout << ans;
}

感觉讲的很模糊，建议多看几遍代码理解一下，我还是太菜了啊。

动态规划

#include <bits/stdc++.h>
using namespace std;
int dp[105][241];
int f[105],s[105],d[105];
int main(){
	int n,h,x;
	cin>>n>>h;h*=12;
	for(int i=1;i<=n;i++) cin>>f[i];
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=2;i<=n;i++){
		cin>>x;
		d[i]=d[i-1]+x;
	} 
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=h-d[i];j++){
			for(int k=1;k<=j;k++){
				if(f[i]-(k-1)*s[i]>0){
					dp[i][j]=max(dp[i][j],dp[i-1][j-k]+k*(f[i]+f[i]-(k-1)*s[i])/2);
				}
			}
		}
	ans=max(ans,dp[i][h-d[i]]);
	}
	cout<<ans;
	return 0;
}