首页 > 代码库 > POJ 3034 DP

POJ 3034 DP

2024-07-15 13:51:59   229人阅读

打地鼠游戏中，你有一个锤子，每一秒钟你可以拿着锤子移动d个单位的距离，必须是直线，掠过的鼠洞中露出的地鼠都会被锤打至，而事先知道从开始时各时间段内出现在老鼠的数量和位置，问题是从游戏开始至结束时，你最多能打到多少只地鼠，开始时锤子可以在任何位置。


题目有个陷阱，

只是说Moles出现的坐标为正,但没说hammer移动的位置要为正,可以为"any position"

所以锤子可以移出矩阵，再从矩阵外一点移进来
例：

20 5 4
1 0 1
0 1 1
0 5 2
1 6 2
0 0 0
答案应该是：4

把n*n矩阵变为  (n+2d)*(n+2d）的矩阵，所有地鼠的x和y各加d，在这个矩阵内DP。

我们把每一秒看成一个状态，则当前时间下，锤子落在各位置上能打到的最多的地鼠为能在一秒内移动至该位置的各位置到达该位置时打到的地鼠数量与出发状态时快打到的地鼠数量之和的最大值。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

struct node
{
    int x,y;
}map[11][1010];

int temp[31][31],dp[2][31][31],time[11];

int Max(int a,int b)
{
    if(a<b) return b;else return a;
}
int gcd(int a,int b)
{
    if (b==0) return a; else return gcd(b,a%b);
}
int cal(int x,int y,int tx,int ty) // 记录在某时间从(x,y)走到(tx,ty） 所产生的价值
{
    int dx,dy,tp,ans;
    if (x==tx && y==ty) return temp[x][y];
    dx=tx-x;
    dy=ty-y;
    tp=gcd(abs(dx),abs(dy));
    dx/=tp;
    dy/=tp;

    ans=0;
    for (x,y;x!=tx || y!=ty;x+=dx,y+=dy)
        ans+=temp[x][y];
    ans+=temp[tx][ty];
    return ans;
}
int main()
{
    int n,d,m,x,y,t,i,j,l,ans,a,b;
    while (scanf("%d%d%d",&n,&d,&m)!=EOF)
    {
        if (n+d+m==0) break;
        memset(map,0,sizeof(map));
        memset(time,0,sizeof(time));
        while (m--)
        {
            scanf("%d%d%d",&x,&y,&t);
            time[t]++; //记录时间ｔ一共出现了多少地鼠
            map[t][time[t]].x=x+d; // 记录时间t出现的每一个地鼠
            map[t][time[t]].y=y+d;
        }
        n+=d+d;

        memset(dp,0,sizeof(dp));

        for (i=1;i<=10;i++)
        {
            memset(temp,0,sizeof(temp)); 
            for (j=1;j<=time[i];j++)
                temp[map[i][j].x][map[i][j].y]=1;// 记录时间i出现的地鼠图
            for (j=0;j<n;j++) 
                for (l=0;l<n;l++) // 枚举位置
                {
                    dp[i%2][j][l]=dp[1-i%2][j][l];
                    for (a=-d;a<=d;a++)
                        for (b=-d;b<=d;b++) //枚举移动方式
                        {
                            if (a*a+b*b>d*d) continue;
                            x=a+j;
                            y=b+l;
                            if (x<0 || x>=n || y<0 || y>=n) continue;
                            dp[i%2][j][l]=Max(dp[i%2][j][l],dp[1-i%2][x][y]+cal(x,y,j,l));
                        }
                }
        }
        ans=0;
        for (i=0;i<n;i++)
            for (j=0;j<n;j++)
            ans=Max(ans,dp[0][i][j]);

        printf("%d\n",ans);
    }
    return 0;
}



联系
我们