题意 ： 在一个二维直角坐标系中，有n×n个洞，每个洞的坐标为（x，y）， 0 ≤ x, y < n，给你一把锤子可以打到地鼠，最开始的时候，你可以把锤子放在任何地方，如果你上一秒在（x1，y1），那下一秒直线移动到的整数点（x2，y2）与这个点的距离小于等于d，并且当锤子移动（x2，y2）这个点时，所有在两点的直线上的整点数都可以打到。例如（0，0）移动到（0，3）。如果（0，1），（0，2）有老鼠出现就会被打到。求能够打的最多老鼠。
思路 ： Dp[i][j][k]代表点（i,j）在第k秒最多可以得多少分。等于dp[x][y][k-1]（点（x,y）为任意一个一秒内能到达（i,j）的点）+ 两点确定的直线上出现的地鼠数。求最大值。
//
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm> using namespace std ; int mapp[][][] ;
int dp[][][];
int n , d,m ; int gcd(int a,int b)
{
return (a == ) ? b : gcd(b % a, a) ;
} int getsum(int sx,int sy,int ex,int ey,int t)
{
if(sx == ex && sy == ey) return mapp[sx][sy][t] ;//同一个点
int dx = ex-sx,dy = ey-sy ;
int sum = ;
if(dx == )//如果两个点在同一行
{
if(sy > ey) swap(sy,ey) ;
for(int i = sy ; i <= ey ; i++)
sum += mapp[sx][i][t] ;
return sum ;
}
else if(dy == )//同一列
{
if(sx > ex) swap(sx,ex) ;
for(int i = sx ; i <= ex ; i++)
sum += mapp[i][sy][t] ;
return sum ;
}
else
{
int g = gcd(abs(dx),abs(dy)) ;
dx /= g ;
dy /= g ;
for(int i = ; i <= g ; i++)//这条斜线上的所有整点
sum += mapp[dx * i + sx][dy * i + sy][t] ;
return sum ;
}
}
int main()
{
while(cin >> n >> d >> m)
{
if(n == && d == && m == ) break ;
int x,y,t,tt = ;
memset(dp,,sizeof(dp)) ;
memset(mapp,,sizeof(mapp)) ;
for(int i = ; i < m ; i++)
{
cin >> x >> y >>t ;
mapp[x + d][y + d][t] = ;
tt = max(tt,t) ;
}
n += * d ;//因为锤子可以在某时刻到达盘外边。
for(int t1 = ; t1 <= tt ; t1 ++)
for(int i = ; i < n ; i ++)
for(int j = ; j < n ; j++)
{
int sx = max(i - d,) ;
int sy = max(j - d,) ;
int ex = min(i + d,n - ) ;
int ey = min(n - ,j + d) ;
for(int x = sx ; x <= ex ; x++)
for(int y = sy ; y <= ey ; y++)
if(((x - i)*(x - i)+(y - j)*(y - j)) <= d * d)
dp[i][j][t1] = max(dp[x][y][t1-]+getsum(x,y,i,j,t1),dp[i][j][t1]) ;
}
int maxx = ;
for(int i = ; i < n ; i++)
for(int j = ; j < n ; j++)
maxx = max(dp[i][j][tt],maxx) ;
printf("%d\n",maxx) ;
}
return ;
}