P2285 [HNOI2004] 打鼹鼠

题目：
链接：https://www.luogu.com.cn/problem/P2285
这题感觉如果想不到递推关系可能会很麻烦，因为我之前想到的关系就是用dp存：包含三个维度：times，x，y，即dp[times][x][y]来存，然后递推。
但是如果把dp看作是以p结尾的抓到的耗子数量时就会方便很多

同时要注意，每次到一个点的时候先立为1，因为无论怎么样这个都是肯定可以抓到的
O(n^2),感觉有点水？（

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;

const int N = 1e4 + 1;
int n, m;
struct mouse
{
	int times, x, y;
}mouselst[N];
int dp[N];
bool is_get(mouse a, mouse b)
{
	if (abs(a.x - b.x) + abs(a.y - b.y) <= abs(a.times - b.times))return true;
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++)cin >> mouselst[i].times >> mouselst[i].x >> mouselst[i].y;
	for (int i = 0; i < m; i++)
	{
		dp[i] = 1;//this！important
		for (int j = 0; j < i; j++)
			if (is_get(mouselst[i], mouselst[j]))
				dp[i] = max(dp[i], dp[j] + 1);
	}
	int ans = 0;
	for (int i = 0; i < m; i++)ans = max(ans, dp[i]);
	cout << ans ;
	
	return 0;
}