题解 P1717 【钓鱼】

Sky_Art · 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毕竟我太弱了