停课集训|Whac-a-Mole(动态规划) 数论|动态规划

【停课集训|Whac-a-Mole(动态规划)】
Whac-a-Mole Time Limit:2000MSMemory Limit:65536KB64bit IO Format:%I64d & %I64u POJ 3034 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 mis 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

文章图片

#include #include #include #include //避免出现负数下标构图时 n+d+d？？ #define MAXN 40 using namespace std; struct Point { int x,y; }p[MAXN][1010]; //记录每个时间点，有哪些老鼠int lenth[MAXN]; //每个时间点老鼠的个数 int n,d,m; int x,y,t,ans; int dp[2][MAXN][MAXN]; //因为当前的t与前几秒无关，故用滚动数组记录状态，节省空间 int t_map[MAXN][MAXN]; //当前时间点图上有的老鼠 void init() { freopen("D - Whac-a-Mole.in","r",stdin); freopen("D - Whac-a-Mole.out","w",stdout); }int gcd(int a,int b) { if(a==0)return b; return gcd(b%a,a); }int find_mice(int x,int y,int tx,int ty)//计算从(x,y)到(tx,ty)能打到的老鼠 { int ret=0,dx,dy,tp; //因为只有整数点才有老鼠 //所以通过求两点距离的最大公因数可减少枚举的次数tp=gcd(abs(tx-x),abs(ty-y)); dx=(tx-x)/tp; dy=(ty-y)/tp; //记录个数 for(int i=x,j=y; i!=tx||j!=ty; i+=dx,j+=dy) ret+=t_map[i][j]; /* //不能直接枚举 ///导致无法退出或溢出 for(int i=x,j=y; i!=tx||j!=ty; i++,j++) ret+=t_map[i][j]; */ ret+=t_map[tx][ty]; return ret; } void readdate() { memset(lenth,0,sizeof(lenth)); for(int i=1; i<=m; i++)//读入老鼠 { scanf("%d%d%d",&x,&y,&t); p[t][lenth[t]].x=x+d; p[t][lenth[t]].y=y+d; lenth[t]++; } n+=d+1; //WA——??? //n+=d*2; //AC——？？？ memset(dp,0,sizeof(dp)); for(int i=0; id*d || !dx && !dy) continue; x=i+dx; y=j+dy; if(x<0 || x>=n || y<0 || y>=n) continue; dp[t&1][i][j]=max(dp[t&1][i][j],dp[!(t&1)][x][y]+find_mice(i,j,x,y)); //更新状态 } }} }for(int i=0; ians) ans=dp[0][i][j]; } return ans; } int main() { //init(); while(scanf("%d%d%d",&n,&d,&m)) { if(n==0&&m==0&&d==0)break; readdate(); work(); ans=solve(); printf("%d\n",ans); } return 0; }