文档介绍：打鼹鼠(CSCWorkGroup邀请赛II,来自VIJOS)描述Description根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1,j),(i+1,j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。输入格式InputFormat文件第一行为n(n<=1000),m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。输出格式OutputFormat输出文件中仅包含一个正整数,表示被打死鼹鼠的最大数目。样例输入SampleInput22111222样例输出SampleOutput1知其然:设F[I][I]:=MAX{F[J]+1},能在规定的时间内从第I只鼹鼠到达第J只鼹鼠。知其所以然:其实就是LIS问题。评价:代码要优秀,特别是已接近10的8次方的时候。多了一句话,就可能超时。思考:要善于发现事物的本质。引申:大地的秘密(将一串数排成规定的序列,每次只能移动临近的两个数,求最少移动次数。勇气的足迹仙剑模拟赛),合唱队形(NOIP2004),难解的问题(求解得的LIS必须有第K项。VIJOSP1369).代码:varmax,n,m,p:longint;a:array[0..10000,1..3]oflongint;f:array[0..10000]oflongint;procedurerf;vari,j,x,y,tt:longint;beginassign(input,'');reset(input);readln(n,m);fori:=1tomdobeginreadln(tt,x,y);if(x>0)and(y>0)and(x<=n)and(y<=n)thenbegininc(p);a[p,1]:=tt;a[p,2]:=x;a[p,3]:=y;end;end;close(input);end;proceduremain;vari,j:longint;beginfori:=1topdof[i]:=1;fori:=1topdoforj:=i-1downto1doiff[j]+1>f[i]thenifa[i,1]-a[j,1]>=abs(a[i,2]-a[j,2])+abs(a[i,3]-a[j,3])thenf[i]:=f[j]+1;fori:=1topdoiff[i]>maxthenmax:=f[i];end;procedurewf;beginassign(output,'');rew