3085 蚱蜢

蚱蜢"/>

3085 蚱蜢

Task
n*n的矩阵，初始位置在x，y，按照以下要求遍历:
下一步为x1,y1
① |x-x1|=1,|y-y1|>1或|y-y1|=1,|x-x1|>1
② Val[x1][y1]>val[x][y]
求最多遍历的位置个数。
50% n<=100
80% n<=1000
100% n<=1500,val<=1e6

Solution
观察条件②每个点向权值大的数转移。假如在序列中，相当于求单调递增子序列的最大长度（LIS）。题目是LIS的变形，转化成在矩阵中，有转移的限制条件①。

如果从点( i ,j )转移，如果不是从起点到( i , j )的最长长度，一定不是最优的，用这个长度更新其他点是没有意义的。因此对于每个点( I , j )我们需要的信息只有从源点到达(I,j)的最长长度（最优的信息），可以用dp处理。

50分暴力dp：
对于两个限制条件，先确定一个，再枚举另一个。
复杂度O(n^3)
当前点只可能从权值比它小的点转移过来，因此按照权值排序，处理当前i点，所有权值比它小的点都已经处理完毕，枚举符合条件的点，转移即可。

70分树状数组前后缀优化:
如果画出转移的图形，可以发现转移的是四周4行4列的前缀后缀信息。
树状数组可以胜任前缀后缀信息的维护。

100分正难则反 存最值
正难则反，不是考虑哪些点能转移，而是考虑哪些点不能转移，会发现，当前点对于每一行每一列不能转移的只有3个点。如果对于 每一行每一列都存最大的前4个，根据抽屉原理，必定可以找到一个转移，而且是最大的。

对于权值相同会互相影响结果的一段区间，为了避免这种影响，我们采用这一段区间都先查询完，再更新，更新时采用插入排序，找到第一个小的点，后面的点都往后移动一格，这样比每次swap更优。

这里的排序可以采用计数排序,O( n )!！
Cnt[i]表示权值<=i的个数,A[cnt[i]–]=i;
适用于权值种类不大（可以离散）的排序。

const int M=1505;
int rx[]={-2,-2,-1,1,2,2,1,-1},ry[]={1,-1,-2,-2,-1,1,2,2},rz[]={0,0,0,0,1,1,1,1};
int n;
/* 树状数组优化前缀 */
struct Tree{int bit[2][M];