//这道题我们首先有一个O(n*n*m)的暴力DP，然后它死了
//接下来考虑优化
//其实我们根本不考虑某一时刻机器人在哪，我们只要确保它能到一个位置就好了
//于是可以对于每一只老鼠，我们枚举机器人上一只打的是谁
//于是我们有了O(m*m)的算法
#include<cstdio>
using namespace std;
int dp[10010],x[10010],y[10010],t[10010];
int Abs(int x)
{
    if(x>0)
     return x;
    return -x;
}
int Max(int x,int y)
{
    if(x>y)
     return x;
    return y;
}
int main()
{
    int n,m,i,j,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
        dp[i]=1;
        for(j=1;j<i;j++)
         if(Abs(x[i]-x[j])+Abs(y[i]-y[j])<=t[i]-t[j])
          dp[i]=Max(dp[i],dp[j]+1);
    }
    for(i=1;i<=m;i++)
     ans=Max(ans,dp[i]);
    printf("%d",ans);
    return 0;
}

const
maxn=1000;
maxm=10010;
var
t,x,y:array[0..maxm]of longint;
f,next:array[0..maxm]of longint;
n,m,ans:longint;

function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;

procedure init;
var
i,tot:longint;
begin
read(n,m);
tot:=0;
for i:=1 to m do
begin
inc(tot);
read(t[tot],x[tot],y[tot]);
if (x[tot]<=0)or(x[tot]>n)or(y[tot]<=0)or(y[tot]>n) then dec(tot);
end;
m:=tot;
next[0]:=m+1;
end;

procedure work;
var
i,j,k:longint;
begin
for i:=1 to m do
begin
j:=0;
k:=0;
while next[j]<>m+1 do
begin
if t[i]-t[next[j]]>=abs(x[i]-x[next[j]])+abs(y[i]-y[next[j]]) then break;
if f[next[j]]<f[j] then k:=j;
j:=next[j];
end;
f[i]:=f[next[j]]+1;
next[i]:=next[k];
next[k]:=i;
ans:=max(ans,f[i]);
end;
writeln(ans);
end;

begin
init;
work;
end.

用longlong竟然超时，用龙就过了。。。。。

program p1441;
var
a,b,t,f:array[1..10000]of longint;
i,j,n,m,ans:longint;
begin
filldword(f,sizeof(f)shr 2,1);
readln(n,m);
for i:=1 to m do readln(t[i],a[i],b[i]);
for i:=1 to m do for j:=1 to i-1 do
if (abs(a[j]-a[i])+abs(b[j]-b[i])<=(t[i]-t[j]))and(f[j]+1>f[i])
then f[i]:=f[j]+1;
for i:=1 to m do if f[i]>ans then ans:=f[i];
writeln(ans);
end.
15行

农夫山泉有点甜。
我看楼上有些大神都是0ms秒杀的……汗……
本人比较朴素，所以写法上复杂度有点高，不过还是过了，哈哈！
补充：下面的代码有残缺，要自己写哦！
var
i,j,k,m,n,max:longint;
a:array[1..10000,1..2] of longint;
b,c:array[0..10000] of longint;
begin
readln(n,m);
for i:=1 to m do readln(c[i],a[i,1],a[i,2]);
for i:=1 to m do b[i]:=1;
for i:=1 to m do
for j:=1 to i-1 do
begin
if ((abs(a[j,1]-a[i,1])+abs(a[j,2]-a[i,2]))<=(c-c))and(a[i,1]<=n)
and(a[i,2]<=n)and(a[i,1]>0)and(a[i,2]>0)and(b[j]+1>b[i])
then b[i]:=b[j]+1;
end;
for i:=1 to m do if b[i]>max then max:=b[i];
writeln(max);
end.

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 976 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 976 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 980 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 980 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 976 KiB, score = 10
测试数据 #6: Accepted, time = 42 ms, mem = 980 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 980 KiB, score = 10
Accepted, time = 134 ms, mem = 980 KiB, score = 100
YES！下面为题解

能绝对AC
type
node=record
f,t,x,y:longint;
end;
var max,i,j,n,m:longint;
t:node;
a:array[0..10000]of node;
begin
readln(n,m);
for i:=1 to m do readln(a[i].t,a[i].x,a[i].y);
for i:=1 to m do
begin
max:=0;
for j:=i-1 downto 1 do
if a[j].f>=max then
begin
if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=a[i].t-a[j].t)then
max:=a[j].f;
end
else break;
a[i].f:=max+1;
j:=i;
while a[j].f<a[j-1].f do begin t:=a[j];a[j]:=a[j-1];a[j-1]:=t;dec(j);end;
end;
write(a[m].f);
end.

这道题其实是湖南省选的原题

记录号 Flag 得分 记录信息

R1745955 Accepted 100 From 国防安全员001－ P1441

环境 评测机 程序提交时间

FPC Evolution SmdCn 2009-11-14 10:17:18

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 384ms

├ 测试数据 06：答案正确... 478ms

├ 测试数据 07：答案正确... 572ms

├ 测试数据 08：答案正确... 462ms

├ 测试数据 09：答案正确... 525ms

├ 测试数据 10：答案正确... 431ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3252ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

转移方法见楼下

f[i]:=f[j]+1 (abs(x[i]-x[j])+abs(y[i]-y[j])

此题很经典啊

f[i]:=f[j]+1 (abs(x[i]-x[j])+abs(y[i]-y[j])=max 一定要有等号！ 0.2s

此题总结：神题！Orz...

结合了三种优化方法一次秒杀：状态、方向和决策

————————————————————

以上是我为此题写给自己的总结

以此纪念此题的各种状态和优化

可能写得不清楚……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

比神牛的短一点吧~~~

type

node=record

f,t,x,y:longint;

end;

var

max,i,j,n,m:longint;

t:node;

a:array[0..10000]of node;

begin

assign(input,'mole.in');reset(input);

assign(output,'mole.out');rewrite(output);

readln(n,m);

for i:=1 to m do readln(a[i].t,a[i].x,a[i].y);

close(input);

for i:=1 to m do

begin

max:=0;

for j:=i-1 downto 1 do

if a[j].f>=max then

begin

if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 134ms

果真，顺推3个点，逆推就磕磕绊绊过了，虽然没秒，但是快很多啊！

难道倒着循环 比 正着循环快那么多~~？？？！！神奇~~~~

C++注意输入输出 及 常数级的优化

没想到这么个常数优化吗m^2的就过了。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：222ms

同样的程序,PUPPY与SUNNY真得没法比

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 509ms

├ 测试数据 05：答案正确... 509ms

├ 测试数据 06：答案正确... 494ms

├ 测试数据 07：答案正确... 509ms

├ 测试数据 08：答案正确... 509ms

├ 测试数据 09：答案正确... 494ms

├ 测试数据 10：答案正确... 509ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3533ms

类似于导弹拦截。

宋氏优化太神奇了，我太弱菜，实在配不上用。

极其严重之膜拜curimit宋神牛之无敌优化

var

n,m,shijian,heng,zong,i,j,max:longint;

a,x,y,zhouoi:array[-10..10000]of longint;

begin

readln(n,m);

for i:=1 to m do

begin

readln(a[i],x[i],y[i]);

end;

for i:=1 to m do

begin

for j:=i downto 1 do

begin

if (a[i]-a[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))

and(zhouoi[j]+1>zhouoi[i])

then begin zhouoi[i]:=zhouoi[j]+1;

if max

尽然没秒kill？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

o(╯□╰)o

严重膜拜curimit神牛的优化方法！太强大了！