【算法】钓鱼问题

icesheep

一水平路边有 n 个钓鱼湖，佳佳有 H 小时的空余时间，他希望这段时间钓尽可能多的鱼。
佳佳从湖1处出发向右走，并有选择地在一些湖边停留，最终在某个湖边结束钓鱼。
佳佳从第 i 个湖走到第 i+1 个湖需要花费 5ti 分钟；并且在第 i 个湖，第一个5分钟可以钓到 Fi 条鱼，之后每分钟能钓到的鱼减少 Di 条。

给出一个算法，如何计算出能钓最多鱼的方案。

hbghlyj

算法思路
1、钓鱼结束必定以1-n个湖结束，则可以将这n种情况全部枚举，求最大值

2、对于以第t个湖结束的，我们假设钓鱼的时间片段有k个(每个片段5分钟)，假设每个湖都钓k个片段，则共有t*k个记录，我们用三元组(f, i, j)存取该记录，三元组表示第i个湖在该湖上第j个时间片段钓了f条鱼

3、将t*k个三元组排序，选取f最大的k个，相加就是一次结果。（因为对于每个湖来说，随着时间的增加，我们钓的鱼数量f是随着时间j增加而减少的，所有当我们对这t*k个三元组按照f排序的时候，对于同一个湖i，其j小的一定会被j大的优先选到，则我们选到的k个三元组，可以根据i值分成t波，每一波都是从j=1递增选取的，最后产生的序列即为本次结果如何选取的序列）