poj3034--Whac-a-Mole(dp)
poj3034--Whac-a-Mole(dp)
题目大意:砸地鼠游戏,n*n的方格,锤子每次最多移动d,地鼠在t时刻出现在(x,y)时间,维持一个单位时间,不会在同一时间同一位置出现两只老鼠,锤子可以砸经过的地鼠,问最多可以砸多少地鼠。(初始锤子可以在任意位置)
dp[t][i][j]:t时刻在锤子在(i,j)位置时能砸到的最多的地鼠个数
状态转移方程:因为锤子最多移动d,所以枚举(x-d,y-d)到(x+d,y+d)的点(tx,ty),认为这是(x,y)向(tx,ty)移动的第一个点,然后计算在d范围内的点。统计被砸的地鼠的个数
注意:肯能通过边界外的点进行移动
20 5 4 1 0 1 0 1 1 0 5 2 1 6 2 0 0 0 结果是4所以要将所有的点移动(5,5)的距离,可以避免负坐标
#include #include #include using namespace std ; int dp[12][41][41] ; int Map[12][41][41] ; void f(int n,int t,int x,int y,int d) { int i , j , k , p , q , num ; for(i = max(0,x-d) ; i <= min(n-1,x+d) ; i++) { for(j = max(0,y-d) ; j <= min(n-1,y+d) ; j++) { if( i == x && j == y ) continue ; p = i - x ; q = j - y ; k = num = 0 ; while( x+k*p >= 0 && x+k*p < n && y+k*q >= 0 && y+k*q < n && k*k*(q*q+p*p) <= d*d ) { if( Map[t][x+k*p][y+k*q] ) num++ ; dp[t][x][y] = max(dp[t][x][y],dp[t-1][x+k*p][y+k*q]+num) ; k++ ; } } } return ; } int main() { int n , d , m ; int x , y , t ; int i , j , max_t , ans ; while( scanf(%d %d %d, &n, &d, &m) && n+d+m != 0 ) { memset(dp,0,sizeof(dp)) ; memset(Map,0,sizeof(Map)) ; max_t = ans = 0 ; while( m-- ) { scanf(%d %d %d, &x, &y, &t) ; Map[t][x+5][y+5] = 1 ; max_t = max(max_t,t) ; } n += 12 ; for(t = 1 ; t <= max_t ; t++) { for(i = 0 ; i < n ; i++) { for(j = 0 ; j < n ; j++) { f(n,t,i,j,d) ; ans = max(ans,dp[t][i][j]) ; } } } printf(%d , ans) ; } return 0 ; }企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:上海网站制作 http://www.flpsz.com
人气文章
10-08
·习近平访美首日:三个“小故事”阐释...11-05
·网络拍卖被指夸大宝贝价值收取高额费...11-26
·9月辽宁省通报71起违规发福利等问题|...09-15
·媒体揭秘开学首日坠亡女教师从举报到...05-17
·侨界关注:华人如何突围“平行之国”...07-06
·煤电行业医保将纳入地方管理 涉河|...07-27
·106家中国企业上榜2015《财富》世界5...09-18
·叙利亚3岁男童偷渡溺亡拍摄者讲照片...10-26
·不限购城市首套房贷首付降至25% 业...09-06
·WebService体系之——HelloWorld搭建11-24
·女大学生亚丁游玩失踪 景区通知扩大...01-08
·女生太邋遢 被室友“群殴”致十级伤残|07-30
·陕西一家医院科室过度医疗 负责人被...07-17
·重庆单独两孩实施后年均5万对夫妇|爱...10-28
·得润电子等九公司高管“限卖令”下顶...08-20
·球迷因国足丢球心脏病发被送医 现场...12-30
·苏州蔬菜因冷空气上涨一成多 产量到...06-25
·迷信男看遗照后疑自己“鬼上身” 为...07-06
·女子怀孕六月却不知男友真名 婚期被...07-08
·谢娜光脚上《偶像来了》 获林青霞肯...