[낙곡] P2285 [HNOI2004] 두더지 잡기(#선형 dp)

제목 설명
두더지는 구멍을 파는 것을 매우 좋아하는 동물이지만, 일정한 시간이 지나면 머리를 땅에 내밀어 바람을 쐬는 것을 좋아한다.이 특징에 따라 소는 두더지를 잡는 놀이를 만들었다. n*n의 격자에서 어떤 순간에 두더지는 특정한 격자에서 머리를 내밀어 바람을 쐬곤 한다.너는 로봇을 제어해서 두더지를 잡을 수 있다. 만약 i시간에 두더지가 어떤 격자에 나타나고 로봇도 같은 격자에 있으면 이 두더지는 로봇에 의해 맞아 죽는다.로봇은 매 순간 한 칸만 이동하거나 제자리에 머물 수 있다.로봇의 이동은 현재 있는 격자에서 인접한 격자로 이동하는 것을 말한다. 즉, 좌표가 (i, j)인 격자에서 (i-1, j), (i+1, j), (i, j-1), (i, j+1) 네 개의 격자로 이동하고 로봇은 전체 n*n의 격자를 빠져나갈 수 없다.게임이 시작되면 로봇의 초기 위치를 자유롭게 선택할 수 있다.
지금은 한동안 두더지가 나타나는 시간과 장소를 알고 있습니다. 로봇이 이 시간 안에 가능한 한 많은 두더지를 죽일 수 있도록 프로그램을 작성해 주십시오.
입력 형식
파일 input.txt에서 데이터를 읽으면 파일의 첫 번째 행동 n(n<=1000), m(m<=10000)을 나타낸다. 그 중에서 m는 이 기간 동안 나타난 두더지의 개수를 나타낸다. 다음 m줄에는 세 개의 데이터 타임이 있고 x, y는 한 마리의 두더지가 게임이 시작된 후 타임이 있고 x줄 y의 격자에 두더지 한 마리가 나타났다는 것을 의미한다.Time은 증가 순서로 표시됩니다.같은 시간에 여러 마리의 두더지가 나타날 수 있지만 같은 시간에 같은 장소에서 한 마리의 두더지만 주의해라.
출력 형식
출력 파일 output.txt에는 두더지를 죽인 최대 수를 나타내는 정수만 포함되어 있습니다.
출력 샘플 가져오기
#1 복사 입력

2 2	         
1 1 1		
2 2 2

출력 #1 복사

1

사고의 방향
처음에는 3차원 dp로 하려고 했는데 생각만 해도 터질 것 같아.3차원 dp의 상태 정의는 dp[i][j][k]를 로봇이 (i, j)에 도착할 때 소모되는 시간이 k일 때 가장 많이 칠 수 있는 두더지의 양은 얼마인지이다.
dp[i]로 하여금 두 번째 두더지, 최대 몇 마리의 쥐를 잡을 수 있는지 표시하도록 한다.i번째 시점 이전의 임의의 시점에서 이동할 수 있음을 쉽게 알 수 있다.
dp[i]=min(dp[i],dp[j]+1)
이게 LIS가 아니라는 걸 발견했어?!네, 제목이 우리에게 시간을 점차적으로 늘리는 순서대로 제시하기 때문입니다.
언제든지 두더지 한 마리를 죽일 수 있기 때문에 임의로 dp[i]=1.
이 문제는 도착 여부와 관련이 있기 때문에 이동하기 전에 맨해튼의 거리가 시간차보다 작은지 판단한다.

#include 
#include 
#include 
#include 
#define maxn 10001
using namespace std;
int dp[maxn],n,m,s;
struct mouse
{
	int x,y,t;
}a[maxn];
inline int dis(int x,int y)//      
{
	return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register int i,j,k;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>a[i].t>>a[i].x>>a[i].y;
		dp[i]=1;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j