1 //Accepted    260 KB    579 ms 2 //题目中给出moles不会出现在负坐标上，但是没说hammer不会出现在负坐标上（简直就是扯淡） 3 //考虑到hammer最大的移动距离是d，把坐标都右移d，剩下的就是dp了 4 //dp[i][j][t]表示t时间hammer在（x,y）处能够得到的最大值 5 //dp[i][j][t]=max(dp[x][y][t-1]+count) 6 //其中(i,j)和(x,y)之间的距离小于等于d 7 //count表示两点之间在t时刻mole的数量 8 #include <cstdio> 9 #include <cstring>10 #include <iostream>11 using namespace std;12 const int imax_n = 32;13 const int imax_t = 12;14 int appearance[imax_n][imax_n][imax_t];15 int dp[imax_n][imax_n][imax_t];16 int n,m,t,d;17 int max_t;18 int max(int a,int b)19 {20     return a>b?a:b;21 }22 int min(int a,int b)23 {24     return a>b?b:a;25 }26 void Dp()27 {28     memset(dp,0,sizeof(dp));29     for (int t=0;t<=max_t+1;t++)30     {31         for (int i=0;i<n+2*d;i++)    //考虑到hammer可以移动到moles出现以外的地方，dp的范围扩大2*d32         {33             for (int j=0;j<n+2*d;j++)34             {35                 dp[i][j][t]=dp[i][j][t-1];36                 for (int x1=i-d;x1<=i+d;x1++)37                 {38                     if (x1<0) continue;39                     if (x1>n+2*d) break;40                     for (int y1=j-d;y1<=j+d;y1++)41                     {42                         if (y1<0) continue;43                         if (y1>n+2*d) break;44                         if ((i-x1)*(i-x1)+(j-y1)*(j-y1)>d*d) continue;45                         int start_x,start_y,end_x,end_y;46                         start_x=min(i,x1);47                         end_x=max(i,x1);48                         start_y=min(j,y1);49                         end_y=max(j,y1);50                         int count=0;51                         for (int x2=start_x;x2<=end_x;x2++)52                         for (int y2=start_y;y2<=end_y;y2++)53                         if ((x1-i)*(y2-j)==(x2-i)*(y1-j))54                         count+=appearance[x2][y2][t];55                         dp[i][j][t]=max(dp[i][j][t],dp[x1][y1][t-1]+count);56                     }57                 }58             }59         }60     }61     int ans=0;62     for (int i=0;i<n+2*d;i++)63     for (int j=0;j<n+2*d;j++)64     ans=max(ans,dp[i][j][max_t+1]);65     printf("%d\n",ans);66 }67 int main()68 {69     while (scanf("%d%d%d",&n,&d,&m),n+m+d)70     {71         int x,y,t;72         max_t=0;73         memset(appearance,0,sizeof(appearance));74         for (int i=0;i<m;i++)75         {76             scanf("%d%d%d",&x,&y,&t);77             appearance[x+d][y+d][t]=1;78             max_t=max(max_t,t);79         }80         Dp();81     }82     return 0;83 }