poj3034Whac-a-Mole(dp)

2023-11-10 16:40

文章标签 dp poj3034whac mole

本文主要是介绍poj3034Whac-a-Mole(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接

状态转移好想不过有坑大家都犯的错误我也会犯很正常

就是锤子可以移到n*n以外要命的是我只加了5 以为最多不会超过5 WA了N久才想到上下两方向都可以到5 所以最多加10

以时间和坐标进行DP

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define N 1010
 9 #define M 32
10 struct node
11 {
12     int x[N],y[N];
13 }f[M][M];
14 int o[12][M][M];
15 int dp[12][M][M];
16 int n,nu[M][M];
17 int dis(int x1,int y1,int x2,int y2)
18 {
19     if(x1<0||x1>=n+10||y1<0||y1>=n+10)
20     return -1;
21     int s;
22     s = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
23     return s;
24 }
25 int main()
26 {
27     int i,j,g,k,d,kk,m;
28     while(scanf("%d%d%d",&n,&d,&m)!=EOF)
29     {
30         if(n==0&&d==0&&m==0)
31         break;
32         memset(dp,0,sizeof(dp));
33         memset(o,0,sizeof(o));
34         memset(nu,0,sizeof(nu));
35         int maxz = 0;
36         int a,b,c;
37         for(i = 1; i <= m ; i++)
38         {
39             scanf("%d%d%d",&a,&b,&c);
40             o[c][a+5][b+5] =1;
41             maxz = max(maxz,c);
42         }
43         int ans=0;
44         for(i = 0 ; i < n+10 ; i++)
45             for(j = 0 ;j < n+10 ; j++)
46             {
47                  int po = 0;
48                  for(k = -d; k <= d; k++)
49                     for(kk = -d; kk <= d ; kk++)
50                     {
51                         int tx = i+k;
52                         int ty = j+kk;
53                         if(dis(tx,ty,i,j)!=-1&&dis(tx,ty,i,j)<=d*d)
54                         {
55                             po++;
56                             f[i][j].x[po] = tx;
57                             f[i][j].y[po] = ty;
58                             nu[i][j] = po;
59                         }
60                     }
61             }
62         for(i = 1 ;i <= maxz ; i++)
63             for(j = 0; j < n+10 ; j++)
64                 for(g = 0 ; g < n+10 ; g++)
65                    for(k = 1; k <= nu[j][g] ; k++)
66                    {
67                        int tx = f[j][g].x[k];
68                        int ty = f[j][g].y[k];
69                        int x1 = min(tx,j),x2 = max(tx,j);
70                        int y1 = min(ty,g),y2 = max(ty,g);
71                        int num = 0;
72                        for(kk = x1; kk <= x2 ; kk++)
73                         for(int mm = y1 ; mm <= y2 ; mm++)
74                         {
75                             if((ty-g)*(kk-j)==(tx-j)*(mm-g)&&o[i][kk][mm])
76                             num++;
77                         }
78                         dp[i][tx][ty] = max(dp[i][tx][ty],dp[i-1][j][g]+num);
79                         ans = max(ans,dp[i][tx][ty]);
80                     }
81         printf("%d\n",ans);
82     }
83     return 0;
84 }