luogu 2285 打鼹鼠

S1

看到这道题的时候其实我是懵逼的。
第一眼感觉是大模拟或者搜。脑海里立马出现了一个n*n的矩阵，然后一个机器人在那走来走去打鼹鼠，如果我一直这么想下去的话估计很难出正解。

S2

看到refun的题解
这个题其实和矩阵毛关系都没有，而实质是一个最长上升子序列一类的问题，如果j点能够到达i点，那么直接f[i]=max(f[i],f[j]+1);即可。
实现的时候出现了点问题，都忘了LIS怎么打了……没有将f[i]都初始化为1，GG。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib> 
#define rint register int
#define inv inline void
using namespace std;
int n,m,t[10001],x[10001],y[10001],f[10001];
int main()
{
	scanf("%d%d",&n,&m);
	for (rint i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	f[1]=1;int ans=1;
	for (rint i=2;i<=m;i++)
	{
		f[i]=1;
		for (rint j=1;j<=i-1;j++)
			if (abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])
				f[i]=max(f[i],f[j]+1);
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
}