贪心例题

对于这类贪心问题,可以先对只有一个鱼塘时最大钓鱼量是多少，再增加第二个，有两个鱼塘时最大钓鱼量是多少，一直到第 n 个^[1] (注:增加到第 i 个时需要减去相应的路上花费的时间)

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int fish[N],d[N],vis[N],s[N];
int n,h,k,ans;
bool cmp(int a,int b){return a>b;}
int main(){cin>>n>>h;
	for(int i=1;i<=n;i++)cin>>fish[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=2;i<=n;i++)cin>>vis[i];
	vis[1]=0;h*=12;
	for(int i=1,x;i<=n;i++){
		h-=vis[i];//去掉走到第i个时花费的时间 
		if(h<=0)break;
		for(int j=fish[i],t=1;j>0&&t<=h;j-=d[i],t++)
			s[k++]=j;//加上该鱼塘能钓的鱼的数量 
		sort(s,s+k,cmp);x=0;
		for(int u=1,v=0;v<k&&u<=h;v++,u++)
			x+=s[v];//从大到小在时间h内能钓鱼的数量 
		if(x>ans)ans=x;
	}cout<<ans;
	return 0;
}