首页 > 代码库 > poj 3034 Whac-a-Mole

poj 3034 Whac-a-Mole

2024-07-09 00:50:55   222人阅读

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 }
View Code

 


联系
我们