贪心整理&一本通1431：钓鱼题解

布满荆棘的人生 2021-11-18 00:18 338阅读 0赞

[题目传送][Link 1]

![1605498-20190607101804138-2069363044.png][]

（[其实有一个更正经的题解][Link 2]）

看了许久，发现这题貌似就是一个动态规划啊，但毕竟是贪心题库里的题，还是想想用贪心解吧。

经过（借鉴大佬思路）十分复杂的思考后，终于理解出了这题的贪心思路。该题的难点主要在最后可在任意湖边停住，而且不能往回走，在一个湖钓鱼时的效率还会越来越少。常规的思路看来是不行的了，题目好多动态未知的量，唯有我们更换角度，“化动为静”：

即然最后不知道停在哪个湖，那就分类讨论呗。把停在每个湖的最优解全部求出，在最后取个最优解不就行了吗？发现当我们知道主人公最后停在哪个湖后，她的路径也就唯一确定了（例如佳佳最后停在了第i个湖，那么她的路径一定是1—》2—》3—》。。。—》i），同时她的纯钓鱼时间可由总空闲时间减去行程时间唯一确定。考虑从哪个湖钓鱼一个5分钟，就相当于在路径1—》2—》3—》。。。—》i中的一个节点上“堆”上一个标记表示在这个湖又钓了5分钟的鱼，显然这里可用贪心策略，每次标记目前为止五分钟钓鱼数目最大的那个湖，并使当前记录答案的sumi\+=在那个湖又钓的鱼数。最后比较所有的sumi(i=1,2,...,n)取最大的输出就行了。

还不懂？也许看看AC代码就懂了：

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cctype>
     4 #include<vector>
     5 using namespace std;
     6 
     7 int ans;
     8 
     9 vector<int>fish,lesss,t;//每个湖第一个 5 分钟能钓到鱼的数量，每个湖每钓鱼5分钟较前5分钟钓的鱼数减少的数量，如题意 
    10 vector<int>get,tmpfish;//从第一个湖走到第i个湖所需时间，每个湖的当前5分钟能钓到的鱼数 
    11 
    12 char ch;
    13  
    14 inline int read()//快读（亦名读入优化） 
    15 {
    16     ans=0;
    17     ch=getchar();
    18     while(!isdigit(ch)) ch=getchar();
    19     while(isdigit(ch)) ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    20     return ans;
    21 }
    22 
    23 inline void init()//初始处理动态数组，因为希望动态数组的下标从1开始 
    24 {
    25     fish.push_back(0);
    26     lesss.push_back(0);
    27     t.push_back(0);
    28     get.push_back(0);
    29     get.push_back(0);//注意get数组在主函数是从下标为2的开始处理的，因此需要多填一个0。 
    30     tmpfish.push_back(0);
    31 }//为什么要填0？为了与普通全局数组的性质相同（定义时默认全初始化为0） 
    32 
    33 int main()
    34 {
    35     init();
    36     int n=read(),h=read()*12;
    37     for(int i=1;i<=n;i++) fish.push_back(read());
    38     for(int i=1;i<=n;i++) lesss.push_back(read());
    39     for(int i=1;i<n;i++) t.push_back(read());
    40     for(int i=2;i<=n;i++) get.push_back(get[i-1]+t[i-1]);
    41     int mava,mapo,tmphours,matot=0;//当前贪心找到的最大值，当前贪心找到的最大值对应的下标（即湖的编号），当前纯钓鱼时间，最后的答案。 
    42     for(int i=1;i<=n;i++) tmpfish.push_back(0);
    43     for(int k=1;k<=n;k++)
    44         if(h>get[k])
    45         {
    46             tmphours=h-get[k];//可用的纯钓鱼时间 
    47             for(int i=1;i<=k;i++) tmpfish[i]=fish[i];//初始化 
    48             int sum=0;//记录的当佳佳最后停在第k个湖时的当前答案 
    49             while(tmphours>0)
    50             {
    51                 mava=-2000000000;
    52                 mapo=0;
    53                 for(int i=1;i<=k;i++)//贪心选择 
    54                     if(mava<tmpfish[i])
    55                     {
    56                         mava=tmpfish[i];
    57                         mapo=i;
    58                     }
    59                 if(mava<=0) break;//没鱼可钓就直接退出 
    60                 sum+=mava;
    61                 if(tmpfish[mapo]>lesss[mapo]) tmpfish[mapo]-=lesss[mapo];
    62                 else tmpfish[mapo]=0;
    63                 tmphours--;
    64             } 
    65             if(sum>matot) matot=sum;
    66         }
    67         else break;
    68     printf("%d",matot);    
    69     return 0;
    70 }

--------------------

最后再总结一下贪心吧：

贪心策略的确定：看到题时，可根据生活经验（滑稽）确认一个直觉指引的贪心策略。对付简单题很有用。

关注一下与题目有关的性质（可以是由数学推导的式子，或是题中描述的物品的一些跟生活有关的物理性质）基本跟贪心有关的题都会有找某个方面的最大值或最小值。

贪心策略的证明: 直接数学推导。

假设有一个更优的方案，反证。

玄学占卜

贪心的几点注意：当整体最优解可由局部最优解推出（并不只局限与一种策略）时才可用贪心。（否则用动态规划）

基本能用贪心的动态规划都行，不过一般贪心的复杂度要优于动态规划。

转载于:https://www.cnblogs.com/InductiveSorting-QYF/p/10987715.html

[Link 1]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1431
[1605498-20190607101804138-2069363044.png]: /images/20211116/c6a1ae0eec8447708a02f6913ace0422.png
[Link 2]: https://blog.csdn.net/TYF_wind/article/details/86361484