经典C题目目GoneFishing算法详解及源代码

Gone Fishing算法详解及源码 这道题其实难在读题上，因为这道题的细节太多，往往容易搞混，造成WA的情况，所以，学好英语还是有作用的。 解此题的主要方法是枚举+贪心。刚开

GoneFishing算法详解及源码 这道题其实难在读题上，因为这道题的细节太多，往往容易搞混，造成WA的情况， 所以，学好英语还是有作用的。 枚举+贪心 解此题的主要方法是。刚开始的时候还没想到一个好方法，因为当前鱼最 多的池塘是变化的，而题目所给描述里面的钓鱼又是有顺序的，即：Johnstartsatlake1, buthecanfinishatanylakehewants.Hecanonlytr__elfromonelaketothe nextone,buthedoesnoth__etostopatanylakeunlesshewishesto.所以，不 可能在池塘中间瞬移，所以贪心貌似不能用。 但转念一想，瞬移还是有可能的，当确定了结束池塘ep（endpond）之后（结束池塘 枚举 由1到n），我们便可以把从1到ep的交通费用从h中减去，然后用剩下的时间贪心即可。 因为在分析问题时，对于一个池塘，John在它上面什么时候钓鱼并不重要，所以可以先把 John看成很聪明的人，然后假设他已经知道了在确定了结束池塘后，在每个池塘花多少时 间使收益最大（实际上John是在贪心之后才知道的），这时我们就可以先减去交通费用， 然后在1~ep的池塘中找现在的最大的即可。 这道题还比较容易WA，但最容易WA的地方还是全零的情况。 法，没问题： 2 + 简单题直接枚举结束湖泊贪心选择就可以了 ___ 可以贪心？（反正你要取的是最优解你可以假定自己知道最优解一路走过去的路上就 直接取最优解就可以了） WAA 因为集训的时候这个题目莫名故再一遍以解心头之恨！ usingnamespa__std;timeG++__faint 不能用多次 GoneFishing Solution: //byoyjpArt #include<iostream> #include<queue> usingnamespa__std; constintN=30; structnode{intnf,idx;voidset(intnn,intii){nf=nn;idx=ii;}};