NC20035. [HNOI2004]打鼹鼠
描述
输入描述
第一行为n（n ≤ 1000）, m（m ≤ 10000），其中m表示在这一段时间内出现的鼹鼠的个数，
接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。
Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。
输出描述
仅包含一个正整数，表示被打死鼹鼠的最大数目
示例1
输入:
2 2 1 1 1 2 2 2
输出:
1
C++ 解法, 执行用时: 119ms, 内存消耗: 644K, 提交时间: 2022-03-11 21:30:44
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m;
int t[N],x[N],y[N];
int f[N];
int ans;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>t[i]>>x[i]>>y[i];
f[i]=1;
for(int j=1;j<i;j++){
if(f[i]<f[j]+1&&abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]){
f[i]=f[j]+1;
}
}
ans=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}