jiry_2's Blog

大水题，按照时间sort一下然后用类似于最长不下降子序列的算法水掉，虽然是m2的算法但是并不慢。

program p1207;
	type
		yanshu=record
			time,x,y:longint;
		end;
	var
		x:array[0..10000] of yanshu;
		f:array[0..10000] of longint;
		i,j,n,m:longint;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[i];
			while i<j do begin
				while (i<j) and (x[0].time<=x[j].time) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (x[0].time>x[i].time) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	begin
		readln(n,m);
		for i:=1 to m do
			readln(x[i].time,x[i].x,x[i].y);
		sort(1,m);
		for i:=1 to m do
			f[i]:=1;
		for i:=2 to m do
			for j:=1 to i-1 do
				if (f[j]+1>f[i]) and (abs(x[i].x-x[j].x)+abs(x[i].y-x[j].y)<=x[i].time-x[j].time) then
					f[i]:=f[j]+1;
		j:=0;
		for i:=1 to m do
			if f[i]>j then j:=f[i];
		writeln(j);
	end.