【POJ 3034】 Whac-a-Mole(DP)

【POJ 3034】 Whac-a-Mole(DP)
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 3621
 
Accepted: 1070
Description
While visiting a traveling fun fair you suddenly have an urge to break the high score in the Whac-a-Mole game. The goal of the Whac-a-Mole game is to… well… whack moles. With a hammer. To make the job easier you have first consulted the fortune teller and now you know the exact appearance patterns of the moles.
The moles appear out of holes occupying the n2 integer points (x, y) satisfying 0 ≤ x, y < n in a two-dimensional coordinate system. At each time step, some moles will appear and then disappear again before the next time step. After the moles appear but before they disappear, you are able to move your hammer in a straight line to any position (x2, y2) that is at distance at most d from your current position (x1, y1). For simplicity, we assume that you can only move your hammer to a point having integer coordinates. A mole is whacked if the center of the hole it appears out of is located on the line between (x1, y1) and (x2, y2) (including the two endpoints). Every mole whacked earns you a point. When the game starts, before the first time step, you are able to place your hammer anywhere you see fit.
Input
The input consists of several test cases. Each test case starts with a line containing three integers n, d and m, where n and d are as described above, and m is the total number of moles that will appear (1 ≤ n ≤ 20, 1 ≤ d ≤ 5, and 1 ≤ m ≤ 1000). Then follow m lines, each containing three integers x, y and t giving the position and time of the appearance of a mole (0 ≤ x, y < n and 1 ≤ t ≤ 10). No two moles will appear at the same place at the same time.
The input is ended with a test case where n = d = m = 0. This case should not be processed.
Output
For each test case output a single line containing a single integer, the maximum possible score achievable.
Sample Input

4 2 6
0 0 1
3 1 3
0 1 2
0 2 2
1 0 2
2 0 2
5 4 3
0 0 1
1 2 1
2 4 1
0 0 0

Sample Output

4
2

Source
Nordic 2006
...사흘을 참다가 마침내 참았다==
제목 대의: 두더지 치기...안 해봤어도 다 봤을 거예요. 두더지 기계는 매초에 몇 개의 구멍이 뚫려서 두더지가 많이 맞을수록 점수가 높아요.
먼저 ndm 세 개의 수를 제시하여 각각 두더지 머신 크기(n*n의 행렬, 점은 구멍)를 나타낸다. 유저가 이동할 수 있는 가장 먼 거리 d는 다음에 두더지 수량 m를 설명한다.
m개 두더지의 제시 방식은 x y t이다
i마리의 두더지가 t초에 x, y구멍에서 뚫고 나오는 것을 나타낸다.
규칙은 다음과 같다. 매번 x1, y1에서 x2, y2로 이동할 수 있으며, 두 점 사이의 보증을 요구한다.
직선 거리가 d 보다 작음
이동하는 노선에서 이 초에 뚫고 나온 두더지는 모두 맞을 것이다.
1초 전에는 망치가 임의의 위치에 있을 수 있고, 이후 i초에는 i-1초가 끝날 때만 위치에서 이동할 수 있다
다시 말하면 t초의 경로를 찾아 경로에서 가장 많이 치는 두더지의 수를 충족시킬 수 있다는 것이다.
전방의 고에너지는 바로 사고방식에 들어갔고, 단지 문제를 구하러 왔을 뿐이면 여기까지 하자.
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
————————————————————————————
방법 dp, 매거초와 이 초 망치의 시작점, 그리고 이 시작점에서 원심,
d는 반경이다. 그러면 이 원 안의 모든 점은 이 초에 이 점에서 도착할 수 있다.
동그랗게 그리면 코드가 잘 안 나와서 다른 방식으로 해도 돼요.
이 점과의 가로 좌표 거리 d내에 세로 좌표 거리 d내의 모든 점을 두루 훑어보고 범위를 초과하면 튀어나온다고 판단합니다
이렇게 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루
그리고 아주 웅덩이, 아주 웅덩이, 아주 웅덩이...
, you are able to move your hammer in a straight line to any position (
x
2,
y
2)
move your hammer in a straight line to any position
in a straight line to any position
to any position
any position
any
됐어, 웨이면 해..
데이터 세트 첨부:
4

20 5 4
1 0 1
0 1 1
0 5 2
1 6 2

(DISCUSS가 빌린
PS:마이너스 방향만 넘을 수 있는 게 아니라 n도 넘을 수 있어요!!!
처리 방식은 0~n을 5~n+5로 옮기는 거예요.
그리고 0~5는 -5~0n+5~n+10은 정방향 폭발을 뜻합니다.
코드는 다음과 같습니다.

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

int mp[12][33][33];
int dp[12][33][33];
int tmp[33][33];
int dirx[] = { 1, 1,-1,-1};
int diry[] = { 1,-1, 1,-1};
int d,n;

int dis(int x1,int y1,int x2,int y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

void cal(int t,int x,int y)
{
	int xx,yy;
	for(int i = 0; i <= d; ++i)
		for(int j = 0; j <= d; ++j)
		{
			if(!i && !j)
			{
				dp[t][x][y] += mp[t][x][y];
				tmp[x][y] = dp[t][x][y];
				dp[t+1][x][y] = max(dp[t+1][x][y],dp[t][x][y]);
				//printf("%d:%d,%d %d
",t,x,y,tmp[x][y]);
				continue;
			}
			if(dis(x,y,x+i,y+j) > d*d) continue;
			for(int k = 0; k < 4; ++k)
			{
				if(!i && dirx[k] < 0) continue;
				xx = x+i*dirx[k];
				if(!j && diry[k] < 0) continue;
				yy = y+j*diry[k];
				if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
				int g = __gcd(abs(xx-x),abs(yy-y));
				tmp[xx][yy] = tmp[xx+(x-xx)/g][yy+(y-yy)/g]+mp[t][xx][yy];
				dp[t+1][xx][yy] =  max(dp[t+1][xx][yy],tmp[xx][yy]);
				//printf("%d,%d->%d,%d: %d->%d get:%d
",x,y,xx,yy,tmp[xx+(x-xx)/g][yy+(y-yy)/g],dp[t+1][xx][yy],mp[t][xx][yy]);
			}
		}
}

int main()
{
	//fread();
	//fwrite();

	int m,x,y,t;
	while(~scanf("%d%d%d",&n,&d,&m) && (n+d+m))
	{
		memset(mp,0,sizeof(mp));
		memset(dp,0,sizeof(dp));
		int tim = 0;
		n += 10;
		while(m--)
		{
			scanf("%d%d%d",&x,&y,&t);
			mp[t][x+5][y+5] = 1;
			tim = max(tim,t);
		}

		for(int i = 1; i <= tim; ++i)
			for(int j = 0; j < n; ++j)
				for(int k = 0; k < n; ++k)
					cal(i,j,k);

		int mx = 0;
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
				mx = max(mx,dp[tim+1][i][j]);
		printf("%d
",mx);
	}

	return 0;
}