poj3034Whac-a-Mole(dp)

链接

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

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

以时间和坐标进行DP

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cmath>

 using namespace std;

 #define N 1010

 #define M 32

 struct node

 {

     int x[N],y[N];

 }f[M][M];

 int o[][M][M];

 int dp[][M][M];

 int n,nu[M][M];

 int dis(int x1,int y1,int x2,int y2)

 {

     if(x1<||x1>=n+||y1<||y1>=n+)

     return -;

     int s;

     s = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);

     return s;

 }

 int main()

 {

     int i,j,g,k,d,kk,m;

     while(scanf("%d%d%d",&n,&d,&m)!=EOF)

     {

         if(n==&&d==&&m==)

         break;

         memset(dp,,sizeof(dp));

         memset(o,,sizeof(o));

         memset(nu,,sizeof(nu));

         int maxz = ;

         int a,b,c;

         for(i = ; i <= m ; i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             o[c][a+][b+] =;

             maxz = max(maxz,c);

         }

         int ans=;

         for(i =  ; i < n+ ; i++)

             for(j =  ;j < n+ ; j++)

             {

                  int po = ;

                  for(k = -d; k <= d; k++)

                     for(kk = -d; kk <= d ; kk++)

                     {

                         int tx = i+k;

                         int ty = j+kk;

                         if(dis(tx,ty,i,j)!=-&&dis(tx,ty,i,j)<=d*d)

                         {

                             po++;

                             f[i][j].x[po] = tx;

                             f[i][j].y[po] = ty;

                             nu[i][j] = po;

                         }

                     }

             }

         for(i =  ;i <= maxz ; i++)

             for(j = ; j < n+ ; j++)

                 for(g =  ; g < n+ ; g++)

                    for(k = ; k <= nu[j][g] ; k++)

                    {

                        int tx = f[j][g].x[k];

                        int ty = f[j][g].y[k];

                        int x1 = min(tx,j),x2 = max(tx,j);

                        int y1 = min(ty,g),y2 = max(ty,g);

                        int num = ;

                        for(kk = x1; kk <= x2 ; kk++)

                         for(int mm = y1 ; mm <= y2 ; mm++)

                         {

                             if((ty-g)*(kk-j)==(tx-j)*(mm-g)&&o[i][kk][mm])

                             num++;

                         }

                         dp[i][tx][ty] = max(dp[i][tx][ty],dp[i-][j][g]+num);

                         ans = max(ans,dp[i][tx][ty]);

                     }

         printf("%d\n",ans);

     }

     return ;

 }