3034专题

POJ 3034 DP

打地鼠游戏中,你有一个锤子,每一秒钟你可以拿着锤子移动d个单位的距离,必须是直线,掠过的鼠洞中露出的地鼠都会被锤打至,而事先知道从开始时各时间段内出现在老鼠的数量和位置,问题是从游戏开始至结束时,你最多能打到多少只地鼠,开始时锤子可以在任何位置。 题目有个陷阱, 只是说Moles出现的坐标为正,但没说hammer移动的位置要为正,可以为"any position" 所以锤子可以移出矩阵

POJ 3034 Whac-a-Mole

题意:娱乐场里面的那种打鼹鼠的游戏机。如下图。在n*n的游戏机上,每个整点都可能出现鼹鼠,鼹鼠分为m批出现。每一批鼹鼠出现的时候,如果锤子在点(i,j),则锤子可以移动到以(i,j)为圆心,d为半径的圆内任何一个整点,且移动路径(包括首尾)上的所有鼹鼠都会被打。(注意,锤子可以移动出游戏机的范围)。初始时,锤子可以在任何点,给定n,m,d和所有鼹鼠出现的时间和位置,问所有鼹鼠都出现之后,最多能打