题意:娱乐场里面的那种打鼹鼠的游戏机。如下图。在n*n的游戏机上,每个整点都可能出现鼹鼠,鼹鼠分为m批出现。每一批鼹鼠出现的时候,如果锤子在点(i,j),则锤子可以移动到以(i,j)为圆心,d为半径的圆内任何一个整点,且移动路径(包括首尾)上的所有鼹鼠都会被打。(注意,锤子可以移动出游戏机的范围)。初始时,锤子可以在任何点,给定n,m,d和所有鼹鼠出现的时间和位置,问所有鼹鼠都出现之后,最多能打到多少鼹鼠。
解法:就是一个普通的dp,设d[i][j][k]表示第i批鼹鼠出现后,锤子停留在(j,k)的情况下,能打到最多的鼹鼠数量。
状态转移方程为if(ok(j, k, x1, y1) d[i][j][k] = max(d[i][j][k], d[i-1][x1][y1] + move(i, x1, y1, j, k))。ok(j, k, x1, y1)是判断点(j, k)在不在以(x1, y1)为圆心d为半径的圆内,move(i, x1, y1, j, k)表示第i次鼹鼠出现的时候,锤子从(x1, y1)移动到(j, k)所能打到最多的鼹鼠数。
求解move函数时,由于是整点,用gcd即可求解。
tag:dp
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-18 21:00 4 * File Name: DP-POJ-3034.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <cmath> 10 11 using namespace std; 12 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 const int OO = 10; 15 16 int n, r, m, t; 17 int a[20][40][40]; 18 int d[20][40][40]; 19 20 int abs(int a) 21 { 22 return a > 0 ? a : -a; 23 } 24 25 int gcd(int a, int b) 26 { 27 return b ? gcd(b, a%b) : a; 28 } 29 30 void init() 31 { 32 n += OO; 33 CLR (a); 34 t = 0; 35 int t1, t2, t3; 36 for (int i = 0; i < m; ++ i){ 37 scanf ("%d%d%d", &t1, &t2, &t3); 38 a[t3][t1+OO][t2+OO] = 1; 39 t = max(t, t3); 40 } 41 } 42 43 bool ok(int x1, int y1, int x2, int y2) 44 { 45 int t1 = abs(x1 - x2), t2 = abs(y1 - y2); 46 return (t1*t1 + t2*t2 <= r*r); 47 } 48 49 int move(int k, int x1, int y1, int x2, int y2) 50 { 51 int ret = 0; 52 if (x1 == x2 || y1 == y2){ 53 if (x1 == x2 && y1 == y2) 54 return a[k][x1][y1]; 55 if (x1 == x2){ 56 for (int i = min(y1, y2); i <= max(y1, y2); ++ i) 57 ret += a[k][x1][i]; 58 return ret; 59 } 60 for (int i = min(x1, x2); i <= max(x1, x2); ++ i) 61 ret += a[k][i][y1]; 62 return ret; 63 } 64 65 int xd = x2 - x1, yd = y2 - y1; 66 int dd = gcd(abs(xd), abs(yd)); 67 xd = xd / dd; yd = yd / dd; 68 int time = 0; 69 while (time <= dd){ 70 ret += a[k][x1][y1]; 71 ++ time; 72 x1 += xd; y1 += yd; 73 } 74 return ret; 75 } 76 77 int DP() 78 { 79 CLR (d); 80 for (int i = 1; i <= t; ++ i) 81 for (int x1 = 0; x1 <= n+OO; ++ x1) 82 for (int y1 = 0; y1 <= n+OO; ++ y1) 83 for (int x2 = max(x1-5, 0); x2 <= min(x1+5, n+OO); ++ x2) 84 for (int y2 = max(y1-5, 0); y2 <= min(y1+5, n+OO); ++ y2) if (ok(x1, y1, x2, y2)) 85 d[i][x2][y2] = max(d[i][x2][y2], d[i-1][x1][y1] + move(i, x1, y1, x2, y2)); 86 87 int ret = 0; 88 for (int i = 0; i <= n; ++ i) 89 for (int j = 0; j <= n; ++ j) 90 ret = max(ret, d[t][i][j]); 91 return ret; 92 } 93 94 int main() 95 { 96 while (scanf ("%d%d%d", &n, &r, &m) != EOF && n){ 97 init(); 98 printf ("%d\n", DP()); 99 } 100 return 0; 101 }