同一时刻同一地点只能出现一只鼹鼠，我以为是在说，给出的数据里可能有两个时刻都是t1，那么在递推时要排除掉同一时刻的鼹鼠。特意在循环里加了这样的条件，但是这样反而只能过90%的测试点。
感觉很奇怪。求解答。
思路是这样，ans【i】表示编号为i的鼹鼠被打后 总共打了几只鼹鼠。只要ans【i】初始化为1。然后遍历0到i-1这i只鼹鼠，通过距离和时间差的判断来决定是否更新ans【i】。
下面是AC代码。而对于前面，我有疑问的地方我写在注释里了。
#include<stdio.h>
typedef struct rat{
int x;//位置x
int y;//位置y
int time;//这只鼹鼠出现时刻
}rat;
int n;
int judge(int i,int j,rat r[]){//判断是否可以连续打死鼹鼠i和j
int dx=r[i].x-r[j].x;
int dy=r[i].y-r[j].y;
int dt=r[i].time-r[j].time;
if(dx<0)dx=-dx;
if(dy<0)dy=-dy;
if(dt<0)dt=-dt;
if(dx+dy<=dt)return 1;
return 0;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
rat r[m];
int ans[m];
for(int i=0;i<m;i++){
scanf("%d%d%d",&r[i].time,&r[i].x,&r[i].y);
ans[i]=1;//如果机器人一开始就一直停留在x，y处等着鼹鼠i，这只鼹鼠一定会被打死
for(int j=0;j<i/*&&r[j].time<r[i].time*/;j++)//循环里加了注释的这句之后就只能过90%（这里有问题，按理来说加不加是一样的，我只是想省几个循环）
if(ans[j]+1>ans[i]&&judge(i,j,r))ans[i]=ans[j]+1;
//这个if来更新ans[i]
}
int max=0;
for(int i=0;i<m;i++)if(max<ans[i])max=ans[i];
printf("%d",max);
//如果r[j].time<r[i].time不要，这里可以直接printf(ans[m-1])
return 0;
}
全部评论
(1) 回帖