《钓鱼》解题报告
《钓鱼》解题报告
By sx349
【摘要】
核心算法思想：枚举+贪心
主要数据结构：堆
其他辅助知识：
时间复杂度：3()k O N T
空间复杂度：()O N
【题目大意】
给定N 个特殊的等差递减序列（当数列中的数小于0时，全部为0）。从第一个数列开始，选择Tk 个数，使得其和最大，且这Tk 个数所在数列的编号组成一个不下降的序列。
【算法分析】
看到此题，首先想到的是POJ1042的Gone Fishing ，这两题的思路几乎如出一辙。 显然，我们先考虑最朴素的做法：枚举。
首先，枚举起点，然后逐个点枚举钓鱼时间Ti ，直到时间用完。每一次枚举起点之后所需的时间复杂度不超过1()(2)k
k k T T i T i O C O ==∑，因此整个算法的时间复杂度将达到(2)k T O N ，题目中虽然没有给出Tk ，但是根据这一时间复杂度，我们所能解决的问题只有大概在20k T ≤的范围内，这显然是无法满足要求的。
接下来我们考虑动态规划。用[,]F I J 表示在第I 个池塘钓了第J 分钟的鱼后，前J 分钟所钓到的鱼的最大值，那么我们有
1111
1[,]max max{[,](,([]1))}I
I J K L P K F I J F K L Calc I J L T P --===+=+-++∑ 其中1(,([]1))I P K Calc I J L T P =+-+
+∑表示从第K 个鱼塘走到第I 个鱼塘后开始钓鱼直到第
J 分钟能钓到的鱼的数量，算法复杂度大约在32()k O N T 。在计算前，还可以先用一个
22
()k
O N T 时间复杂度的预处理来计算掉所有的1(,([]1))I
P K Calc I J L T P =+-++∑的值。 这个算法所能解决的范围比之枚举显然大了很多，在没有更好算法的时候显然可以优先考虑，而且在思考时也并没有什么困难。在预处理方面还可以小小的优化一下：其实我们只需
要先用()k O NT 计算出所有的1(,)k
T J Calc I J ，即在第I 个池塘钓J 分钟鱼所用时间，然后再用2()O N 预处理计算出任意两个池塘之间的路程，如此一来时间复杂度进一步降低为22()k O N T 。
最后，类似于POJ1042，我们可以考虑贪心的算法。贪心的算法是基于如下的一种“瞬移”的思想：假设我们钓鱼时，总是在所有鱼塘中当前鱼最多的一个池塘钓鱼，也就是说我们可以任意移动，当然，在钓过一次鱼之后，必须让它减少一定的数量Y[I]。在我们先枚举起点与终点的基础上，就可以忽略掉移动的用时，这样我们就好像在“瞬移”一样。那么为什么可以这样瞬移钓鱼呢？因为我们在某个鱼塘钓鱼之前，这个鱼塘中的鱼数目是不变的。所以，我们什么时候在这个池塘开始钓鱼不重要，我们在上面钓了几分钟鱼才是最重要的。我们可以先根据“瞬移”思想确定一个序列，然后，将这个序列中在同一个池塘钓鱼的序列拉出来，显然，这个序列是从没有钓鱼的状态，也即池中的最大值X[I]开始，然后以Y[I]为等差减小的。显然，将每个池塘的序列按照池塘序号排好，我们总能得到一个可行的序列来钓鱼，而且这个可行的序列又必然是最大的。
这个过程中，所需要的最频繁的操作是取最大值，假设我们采用数组，每次扫一遍进行这个操作，那么复杂度大约为3()k O N T ，略优于动态规划的算法，而且编程复杂度只是略高于枚举而已；但显然，在取最大值操作上，堆是一个不错的选择。用(log )O N N 的时间复杂度建堆之后，每次取最大值操作都是(log )O N 的。这样，贪心的时间复杂度最终为
2(log )k O N T N ，比之动态规划又减小了不少，显然能够解决的数据范围也进一步增大了。
【心得体会】
显然，这道题的形式类似于POJ1042（这道题同时也见于LRJ 的黑书），这对于我们的思路有很大的帮助。但如果没有做过这道题，也许能够考虑到动态规划的算法，显然也是较优的一种。
通过这道题，我有三点体会：其一，算法的适应程度而非简单程度决定了算法的效率，尽管动态规划是一种很优的算法，但是在不一定适合它的题目（比如这一道）中并不一定就一定优于贪心这种看似很简单的算法；其二，编程复杂度和算法复杂度之间要有所取舍。如果在比赛现场，如果Tk 的值并不是特别大，也许我就不采用堆了（当然，堆的编程复杂度也并不是特别高），而就是直接采用数组逐位扫描；其三，要从不一样的角度思考问题，前两种算法仅限于按照题述那样考虑按照顺序在池塘间移动，而贪心算法则是超脱了这一规则，考虑了“瞬移”思想，就使得问题从新的角度得到诠释。
【附录】
【问题描述】
设有n个鱼塘（1≤n≤40），编号为1，2，…n，排列成一排，同时给出三行数：
第一行的n个数，表示开始时每个鱼塘第一分钟可钓到的鱼数；
第二行的n个数，表示每过一分钟，减少的鱼数，减到0为止；
第三行的n个数，表示从第r-1个鱼塘走到第r个鱼塘花费的时间（2≤r≤n, t1 =0）；
同时给出一个截止时间 tk。
钓鱼规则: 可从任何一个鱼塘开始，钓到任何时候均可转移到下一个鱼塘（只能按鱼塘编号从小到大转移）。转移到下一个鱼塘时可以不钓再往下移，但时间需要累计。
例: n=3 tk=14
24 18 19
4 2 3
0 4 3
钓鱼方案可以为：
第①鱼塘钓鱼4分钟可钓到 24+20+16+12=72；
转移到第②个鱼塘用时 4分钟累计 8分钟
钓鱼2分钟可钓到 18+16=34 累计时间 10分钟
转移到第③个鱼塘，用时 3分钟累计 13分钟
钓鱼 1分钟可钓到 19 ，此时累计用时14分钟，时间到。
全部钓到的鱼为： 72+34+19=125 但还有其他方案
【输入输出】
输入：
第一行有n，tk这2个整数，表示鱼塘数和截止时间。（用空格分隔）
接下来共有三行：
x1 x2 x3 ……x n 表示开始时每个鱼塘第一分钟可钓到的鱼数
y1 y2 y3 ……y n 表示每过一分钟，减少的鱼数，减到0为止
t1 t2 ……t n 表示时间，t r 从第r-1个鱼塘走到第r个鱼塘花
费的时间（2≤r≤n, t1 =0）输出：输出到屏幕，一个数，即可钓到的最多鱼数。
【样例】
输入：
3 14
24 18 19
4 2 3
0 4 3
输出：150
【源程序清单】
{
PROG: Angle
LANG: PASCAL
ID: xyj-flash
}
Program Angle;
Var
N,Tk,Tt,I,St,Ep,Sum,Max,MaxI,Ans,J:Longint;
X,Y,T,Xt:Array[0..40] of Longint;
Begin
Read(N,Tk);
Ans:=-MaxLongint;
For I:=1 to N do
Read(X[I]);
For I:=1 to N do
Read(Y[I]);
For I:=1 to N do
Read(T[I]);
For St:=1 to N do
For Ep:=St to N do Begin
Tt:=Tk;
Xt:=X;
Sum:=0;
For I:=St+1 to Ep do
Tt:=Tt-T[I];
For I:=1 to Tt do Begin
Max:=0;MaxI:=St;
For J:=St to Ep do
If Xt[J]>Max Then Begin
Max:=Xt[J];
MaxI:=J;
End;
Sum:=Sum+Xt[MaxI];
Xt[MaxI]:=Xt[MaxI]-Y[MaxI];
If Xt[MaxI]<0 Then Xt[MaxI]:=0;
End;
If Sum>Ans Then Ans:=Sum;
End;
Writeln(Ans);
End.