同一时刻同一地点只能出现一只鼹鼠,我以为是在说,给出的数据里可能有两个时刻都是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) 回帖