上上周的pku1088

哀悼日结束了，但是没有理由忘记逝去的生命，更没理由不继续好好的生活。

上上周做了一个比较有意思的题目，很有记录的必要，因为自己的思路很清晰，解题的速度很快，没有纠缠，从分析到得到一个算法，再到一个更加完善的最终的动态规划的算法。PKU1088滑雪问题。

很明显的一些分析，如果是搜索的话，那么可以求解所有的位置的可滑的最长路径，然后比较得到最长的。另外题目有个很优质的特点，肯定不会有回路，这个很容易反证。直接搜索时间上肯定不可行，而且题目的递归式明显的最优子问题结构：

path(x, y) = (1 + max(path(xnext, ynext)). xnext, ynext是所有地势更低的节点。然而，当从第一个节点开始求解的时候，她会求出那些地势低的节点的解。而且这些解会大量的应用到求解其他节点。不过，把这些最优字结构变成动态规划算法，并不是十分容易，或者说，变成递推的动态规划算法并不十分容易，需要一些分析（引入其他参数，如同图的最短路径算法）。不过明显的算法可以是备忘录的动态规划，递归+表存储。

于是写了一个备忘录的代码，上传，16MS AC.恩题目就解了。

如果直到这一步，这个题目就没什么意思。首先，这个解把所有子文题都解了，那么递推的算法肯定优于备忘录（《算法导论》上对于动态规划讲的很好）。怎么得到递推算法才是有价值的。回过头来分析递归树，一般的，搜索的过程會止步在一些地势最低（相对周围）的点，那么，这就是一个提示：递推是不是可以从那些坑里面开始。猜测可以使用按照地势排序的节点索引作为传说中的第三参数。那么：

最低的点，很显然，就是他自己。

如果当前已经求得一部分解（索引参数

1 + max(f(p)) (p为那些next ynext为周围有过求解的节点，如果都没有，那么就是f(p) = 0）。

因为f(k)不可能经过比她地势高的节点，所以xnext,ynext 属于 f(x小于 k)

一直递推到k = m*n ，就是最高节点。其中需要比较得到最长解。

递推的出来了，但是它需要预先的一个排序，哈哈，好像这个递推并不一定比备忘录更快啊。备忘录其实比一般地推是坏在递归的开销上，而这个是一个常熟因子。却没拼过排序的开销（排序一般都有O(N*logN)）.看来这个参数代价太大了。

当然这个题目可能有更好的解。

另：

公司封闭了所有除了80 之外的包括https端口，没有机会上网了，连blog都发不了，这篇也是tor上来的，慢死了。唉～