Description

在一个(n*n)的网络中,给出(m)个鼹鼠出来的时间和坐标((t,x,y))

机器人每一时间只能向上,向下,向左,向右移一格，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打掉。

求出机器人最多能打的鼹鼠数量。((nle{1000},mle{10000}))

Solution

能够看出来这道题是(dp)，但就是不好设状态。

发现用棋盘或者时间都不好，就只剩鼹鼠了。

我们设(dp[i])表示打掉第(i)个鼹鼠时，最多能打掉几个鼹鼠。那么初始化就设(dp[]=1)，因为至少能打掉打掉一个鼹鼠。

那么转移也很方便了。先把鼹鼠按照时间从小到大排序（因为肯定是先打掉先出现的鼹鼠，再打掉之后的），那么(dp[i]=max{dp[j]+1}(|x_i-x_j|+|y_i-y_j|le{t_i-t_j,j<i}))，(res=max{dp[i]})

时间复杂度(O(m^2))，可以过。