POJ - 2385 Apple Catching解题报告

有个牛，好多题了，都是牛。然后她想吃苹果。有两个树，单位时间，在一棵树上会掉下来一个苹果。她必须在这个时间正好站到了这棵树下，才能吃到这个苹果。现在给你一共有T（1000）个单位时间，以及每个单位时间是哪一颗树上要掉苹果，这个牛可以瞬间从一棵树到达另一棵树下面，但是这种瞬移技能只能释放最多w（30）次 。问你这个牛最多可以吃到多少苹果。（注：牛一开始在1号树下）ps:要是问西瓜就好了，因为西瓜不长在树上···· 

思路：

设a[i][j][k]表示这个牛在第i个苹果掉下来时，在j号树下，用了k次技能，所能得到的最多的苹果数。

递推公式：a[i][j][k]=max(a[i-1][j][k],a[i-1][!j][k-1]); if(v[i]==j)a[i][j][k]++;边界条件：a[1][j][k]；a[i][j][0]；

关于递推公式以及边界条件的解释：

这个牛在第i个苹果掉下来的时候，在第j号树下，用了k次技能。能得到这个状态的上一状态为：这个牛在第i-1个苹果掉下来的时候，在第！j号树下，用了k-1次技能；或者这个牛在第i-1个苹果掉下来的时候，在第j号树下，用了k次技能。（关键也就是这个牛在第i-1个苹果掉下来和第i个苹果掉下来之间，有没有使用技能）然后如果，这个苹果他接到了，就+1呗~

然后是关于边界条件，很适合想想一个三维的表格来储存数组a（虽然想画个三维图，但是用笔画的图烂的掉渣，估计大家也看不清，就自己想象吧），这样的话，如果要推出第i层的一个，就需要知道第i-1层的两个格（沿i轴-1的一个，以及同i-1平面内无相交边的另一个）。这样，在i取1的时候，就找不到对应的i-1平面了，所以要确定边界a[1][j][k]；同样，在k=0时就找不到对应的k-1了，所以也要确定边界a[i][j][0]。另外十分要注意，开始的时候在1号树下面，所以一切在2号数下面翻转0次得到的苹果数都是-inf。 

然后三层循环为什么从外到内的顺序为ikj:还是有些疑问，不过目前对于这道题来看，调换ik的内外层关系并没有发生错误。对于三维图来说，只不过是改变了各个格的数值确定的顺序。然后就是对递推公式理解上就不太好解释了(其实也是可以解释的):一个一个的用技能，在第i个格用技能得到的总金额可以根据在第i-1个格用技能（a[i-1][j][k]）或者不用这个技能（a[i-1][!j][k-1]） 两种情况来确定。