求路线经过最多站点数的推理题

iseemu2009

如图，问题求解。

mathe

这个算法题不算太难。
首先可以用数学做过小优化，也就是次数i的范围可以简单削减一下。我们知道任何数模n会形成周期，周期是phi(n)<n的因子，所以最终点的数目是以2和3为底的最小周期的最小公倍数，必然不超过phi(n).

在计算出每个点的坐标后，就可以对它们按横坐标进行排序，横坐标相同的按众坐标从小到大排列然后在次排序基础上动态规划，计算从坐下角到第k个点经过最多中间点的路径。
计算第k个点时，我们只需要考虑前k-1个点中纵坐标不超过它的纵坐标并且拥有最长路径(经过点数目)的那个点，对它的点数目加1即可。最后同样计算右上角的点。
那么唯一问题就是维护一个怎样数据结构可以让上诉计算尽量高效。
比较有意思的是我们知道计算过程中两个点a和b,如果a的横坐标不大于b，最长路径长度也不大于b，后面计算过程就不需要再考虑a了。所以，计算过程我们留下的必然是一个横坐标递增，最长路径长度递减的序列，需要注意的是，这个序列的纵坐标也必然递减。
然后处理下一个点时，我们可以在序列中查找到纵坐标刚好不超过它的那个点，新点的最长路径就是那个点最长路径加1。然后我们需要将这个新点插入到序列中那个点之后，然后查找序列中所有附近的点，是否有横坐标不超过它，但是路径长度小于它的，删除掉。
由于我们上面过程需要不停从序列中查找纵坐标匹配位置和删除相应位置附近点，最好使用有序堆来实现这个数据结构，使得每次上诉操作复杂度为log(n)