这题是一个水dp。
用类似最长不下降子序列的方法来写。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,f[10005];
struct Node{
int time,a,b;
}a[10005];
int absd(int x){return x>0?x:-x;}
int main(){
freopen("1207.in","r",stdin);
freopen("1207.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a[i].time,&a[i].a,&a[i].b);
}
f[1]=1;
for(int i=2;i<=m;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(absd(a[j].a-a[i].a)+absd(a[j].b-a[i].b)<=a[i].time-a[j].time && f[j]+1>f[i])f[i]=f[j]+1;
}
f[0]=max(f[i],f[0]);
}
printf("%d\n",f[0]);
return 0;
}
评论 (0)
