[luoguP2285] [HNOI2004]打鼹鼠（DP）

传送门

设f[i]表示i个鼹鼠出现后，打死鼹鼠的最大值

动态转移方程：f[i]=max{f[j]+1}，

条件：abs(x[i]-x[j])+abs(y[i]-y[j])<=time[i]-time[j] (j<i)

代码

#include <cstdio>
#include <iostream>
#define N 1001
#define M 10001
#define abs(x) ((x) < 0 ? -(x) : (x))
#define max(x, y) ((x) > (y) ? (x) : (y))

int n, m, ans;
int s[M][3], f[N], mx[N];

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

int main()
{
	int i, j, k, x, y, z;
	n = read();
	m = read();
	for(k = 1; k <= m; k++)
	{
		s[k][0] = read();
		s[k][1] = read();
		s[k][2] = read();
		f[k] = 1;
		for(i = k - 1; i >= 1; i--)
		{
			if(f[k] >= mx[i] + 1) break;
			if(s[k][0] - s[i][0] >= abs(s[k][1] - s[i][1]) + abs(s[k][2] - s[i][2]))
				f[k] = max(f[k], f[i] + 1);
		}
		ans = max(ans, f[k]);
		mx[k] = max(mx[k - 1], f[k]);
	}
	printf("%d
", ans);
	return 0;
}