POJ 3034 Whac-a-Mole（DP）

题意：在一个二维直角坐标系中，有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）的点）+ 两点确定的直线上出现的地鼠数。求最大值。

 1 //3034
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 
 8 using namespace std ;
 9 
10 int mapp[30][30][20] ;
11 int dp[30][30][20];
12 int n , d,m ;
13 
14 int gcd(int a,int b)
15 {
16     return (a == 0) ? b : gcd(b % a, a) ;
17 }
18 
19 int getsum(int sx,int sy,int ex,int ey,int t)
20 {
21     if(sx == ex && sy == ey) return mapp[sx][sy][t] ;//同一个点
22     int dx = ex-sx,dy = ey-sy ;
23     int sum = 0 ;
24     if(dx == 0)//如果两个点在同一行
25     {
26         if(sy > ey) swap(sy,ey) ;
27         for(int i = sy ; i <= ey ; i++)
28             sum += mapp[sx][i][t] ;
29         return sum ;
30     }
31     else if(dy == 0)//同一列
32     {
33         if(sx > ex) swap(sx,ex) ;
34         for(int i = sx ; i <= ex ; i++)
35             sum += mapp[i][sy][t] ;
36         return sum ;
37     }
38     else
39     {
40         int g = gcd(abs(dx),abs(dy)) ;
41         dx /= g ;
42         dy /= g ;
43         for(int i = 0 ; i <= g ; i++)//这条斜线上的所有整点
44             sum += mapp[dx * i + sx][dy * i + sy][t] ;
45         return sum ;
46     }
47 }
48 int main()
49 {
50     while(cin >> n >> d >> m)
51     {
52         if(n == 0 && d == 0 && m == 0) break ;
53         int x,y,t,tt = 0 ;
54         memset(dp,0,sizeof(dp)) ;
55         memset(mapp,0,sizeof(mapp)) ;
56         for(int i = 0 ; i < m ; i++)
57         {
58             cin >> x >> y >>t ;
59             mapp[x + d][y + d][t] = 1 ;
60             tt = max(tt,t) ;
61         }
62         n += 2 * d ;//因为锤子可以在某时刻到达盘外边。
63         for(int t1 = 1 ; t1 <= tt ; t1 ++)
64             for(int i = 0 ; i < n ; i ++)
65                 for(int j = 0 ; j < n  ; j++)
66                 {
67                     int sx = max(i - d,0) ;
68                     int sy = max(j - d,0) ;
69                     int ex = min(i + d,n - 1) ;
70                     int ey = min(n - 1,j + d) ;
71                     for(int x = sx ; x <= ex ; x++)
72                         for(int y = sy ; y <= ey ; y++)
73                             if(((x - i)*(x - i)+(y - j)*(y - j)) <= d * d)
74                                 dp[i][j][t1] = max(dp[x][y][t1-1]+getsum(x,y,i,j,t1),dp[i][j][t1]) ;
75                 }
76         int maxx = 0 ;
77         for(int i = 0 ; i < n ; i++)
78             for(int j = 0 ; j < n ; j++)
79                 maxx = max(dp[i][j][tt],maxx) ;
80         printf("%d
",maxx) ;
81     }
82     return 0 ;
83 }

View Code