解题思路

第一眼看上去觉得要设计一个三维的 DP，$dp[i][j][k]$ 表示在 $(i,j)$ 这个位置上 $k$ 时刻能够打死的最多的鼹鼠。

但是被数据范围卡死。完全开不开数组啊。

然后注意到题目中有句话说保证是按照时间递增序输入的。

想一下，某个鼹鼠能够被打死，是因为他之前被打死的鼹鼠走过来的。

所以只需要考虑每个鼹鼠之前的若干鼹鼠就可。只要两个鼹鼠的距离小于它们出现的时刻只差，那就可以扩展的到。

 

附上代码

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 10003;int n, m, x[maxn], y[maxn], t[maxn], Ans = 1, dp[maxn];inline int ABS(int x) {    return x>0 ? x : -x;}int main() {    cin>>n>>m;    for(int i=1; i<=m; i++) {        cin>>t[i]>>x[i]>>y[i];        dp[i] = 1;        for(int j=i-1; j>=1; j--)            if(ABS(x[j]-x[i])+ABS(y[j]-y[i]) <= t[i]-t[j])                dp[i] = max(dp[j]+1, dp[i]), Ans = max(Ans, dp[i]);    }    printf("%d", Ans);}