首页 > 代码库 > poj 3034 Whac-a-Mole
poj 3034 Whac-a-Mole
http://poj.org/problem?id=3034
题意:打地鼠游戏中,你有一个锤子,每一秒钟你可以拿着锤子移动d个单位的距离,掠过的鼠洞中露出的地鼠都会被锤打至,而事先知道从开始时各时间段内出现在老鼠的数量和位置,问题是从游戏开始至结束时,你最多能打到多少只地鼠,开始时锤子可以在任何位置。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int dp[35][35][35]; 7 int c[35][35][35]; 8 int n,d,m; 9 10 int gcd(int a,int b)11 {12 return (a==0)?b:gcd(b%a,a);13 }14 15 int get(int x1,int y1,int x2,int y2,int t)16 {17 int dx=x2-x1;18 int dy=y2-y1;19 if(dx==0&&dy==0) return c[x2][y2][t];20 int sum=0;21 if(dx==0)22 {23 if(y1>y2) swap(y1,y2);24 for(int i=y1; i<=y2; i++)25 {26 sum+=c[x2][i][t];27 }28 return sum;29 }30 if(dy==0)31 {32 if(x1>x2)swap(x1,x2);33 for(int i=x1; i<=x2; i++)34 {35 sum+=c[i][y1][t];36 }37 return sum;38 }39 int g=gcd(abs(dx),abs(dy));40 dx=dx/g;41 dy=dy/g;42 for(int i=0; i<=g; i++)43 {44 sum+=c[x1+i*dx][y1+i*dy][t];45 }46 return sum;47 }48 49 int main()50 {51 while(scanf("%d%d%d",&n,&d,&m)!=EOF)52 {53 int max1=0;54 memset(dp,0,sizeof(dp));55 memset(c,0,sizeof(c));56 if(n==0&&d==0&&m==0) break;57 for(int i=0; i<m; i++)58 {59 int x,y,t1;60 scanf("%d%d%d",&x,&y,&t1);61 max1=max(max1,t1);62 c[x+d][y+d][t1]=1;63 }64 n=n+2*d;65 for(int t=1; t<=max1; t++)66 {67 for(int i=0; i<n; i++)68 {69 for(int j=0; j<n; j++)70 {71 for(int x2=0; x2<n ; x2++)72 {73 for(int y2=0; y2<n; y2++)74 {75 if((i-x2)*(i-x2)+(j-y2)*(j-y2)<=d*d)76 {77 int ans=get(x2,y2,i,j,t);78 dp[t][i][j]=max(dp[t][i][j],dp[t-1][x2][y2]+ans);79 }80 }81 }82 }83 }84 }85 int max2=0;86 for(int i=0; i<n; i++)87 {88 for(int j=0; j<n; j++)89 {90 max2=max(max2,dp[max1][i][j]);91 }92 }93 printf("%d\n",max2);94 }95 return 0;96 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。