自动搬运

查看原文

来自洛谷，原作者为

	Sky_Art 缓缓飘落的枫叶像思念 我点燃烛火温暖岁末的秋天

搬运于2025-08-24 21:28:16，当前版本为作者最后更新于2019-02-17 10:42:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

//于2019.10.11修改，代码可AC

朴素贪心

没有什么新算法

也没有用优先队列，线段树bulabula

@ 扶苏

被大佬骂次品题解了啊 QAQ

所以改一下

思路：

枚举终点，贪的是以i为终点的区间中，当前时间最大的鱼数

1. 先算出以每个点为终点的路程时间和（前缀和），从而排除前往其它

   鱼塘的时间的影响（相当于在1到当前点可以随便钓了）

2. 判断该时间点 1到终点的最大 f[i]，时间加五，sum加上

3. 将f[i]减上相应的d值，判断时间是否超出，f[i]是否过小

4. 更新ans

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,sum,t[1000],ans=-1,bj,b[1000],t1;
struct s
{
	int f,d,ti;
}a[1000];

void init()
{

	sum=0;
	for(int i=1;i<=n;i++)
	b[i]=a[i].f;//便于修改当前的鱼数
}
int find(int j)//用来找当前最大的值
{
	int c=-1,bj;
	for(int i=j;i>=1;i--)
	if(c<b[i]) c=b[i],bj=i;//更新最大值
	return bj;
}

int main()
{
	scanf("%d%d",&n,&m);
	m=m*60; //小时转分钟
	for(int i=1;i<=n;i++) scanf("%d",&a[i].f);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].d);
	for(int i=1;i<=n-1;i++) scanf("%d",&a[i].ti);
	for(int i=1;i<=n;i++) 
	t[i]=t[i-1]+a[i-1].ti*5;//计算走到该终点所需时间
	for(int i=1;i<=n;i++)   //^此时以排除路程的时间影响
	{
                t1=t[i];
		init();     //初值
		int j=i;         
		while(1)    //枚举终点
		{
			bj=find(j);   //找到当前f最大值
			if(b[bj]<=0) break;//鱼钓没了
			sum=sum+b[bj];
			b[bj]-=a[bj].d;
			t1+=5;        //时间更新
			if(t1+5>m) break;//时间用完了
		}
		ans=max(ans,sum);
	}
	printf("%d",ans);
}

QAQ毕竟我太弱了