[POJ 3034] | Eurce's Blog

“打地鼠”，好神奇的一题DP…

题意是，有一个n*n的区域，在时刻1~10之间，每时刻会出现一些地鼠。有一个初始位置任意的锤子，在每个时刻，你可以将锤子直线移动最多d个单位，起止点都必须是整点，若有地鼠出现在移动路径上（必须是坐标x,y刚好在直线上），则可以将它们敲掉得分。目标是求t时候后最高得分。

数据规模不是很大，但分析了下复杂度，发现竟然是O(kn^4)级别的……因此需要对某点出发可以移动到的点，以及移动中路过的整点坐标全部预先记录下来……想到这里还觉得太复杂了，怕不是这么做，但是由于d<=5，这样的预处理又是完全合理的……因此开始了一顿乱搞。。。第一次提交WA了之后，读了discuss发现锤子是可以移出区域的。。。稍微作了下修改后便AC了。虽然没有完全能自己想出来，但还是好开心。

#include<cstdio>
#include<cstring>

int n,d,m,ad[30][30],on[30][30][30][30],el;
int b[30][30],dp[30][30],dpt[30][30],t[11];

struct E
{
    int x,y,p;
}e[5000000];

inline int inr(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=d*d;
}

inline int onl(int x1,int y1,int x2,int y2,int x3,int y3)
{
    if(x1==x2) return x3==x1;
    else if(x3==x1&&y3!=y1||x3==x2&&y3!=y2) return 0;
    else return (y3-y1)*(x2-x1)==(y2-y1)*(x3-x1);
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int i,j,k,l,ll,x,y,xx,yy,sc;
    while(~scanf("%d%d%d",&n,&d,&m)&&n)
    {
        memset(ad,-1,sizeof ad);
        memset(on,-1,sizeof on);
        memset(t,-1,sizeof t);
        el=0;
        while(m--)
        {
            scanf("%d%d%d",&i,&j,&k);
            e[el].x=i+5;
            e[el].y=j+5;
            e[el].p=t[k];
            t[k]=el++;
        }
        for(i=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                for(k=0;k<n+10;k++)
                    for(l=0;l<n+10;l++)
                        if(inr(i,j,k,l))
                        {
                            e[el].x=k;
                            e[el].y=l;
                            e[el].p=ad[i][j];
                            ad[i][j]=el++;
                        }
        for(i=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                for(ll=ad[i][j];ll!=-1;ll=e[ll].p)
                {
                    int L,R,D,U;
                    k=e[ll].x;
                    l=e[ll].y;
                    if(i<k) L=i, R=k;
                    else L=k, R=i;
                    if(j<l) D=j, U=l;
                    else D=l, U=j;
                    for(x=L;x<=R;x++)
                        for(y=D;y<=U;y++)
                            if(onl(i,j,k,l,x,y))
                            {
                                e[el].x=x;
                                e[el].y=y;
                                e[el].p=on[i][j][k][l];
                                on[i][j][k][l]=el++;
                            }
                }
        memset(dp,0,sizeof dp);
        for(k=1;k<11;k++)
        {
            memset(b,0,sizeof b);
            memset(dpt,0,sizeof dpt);
            for(l=t[k];l!=-1;l=e[l].p)
            {
                x=e[l].x;
                y=e[l].y;
                b[x][y]=1;
            }
            for(i=0;i<n+10;i++)
            {
                for(j=0;j<n+10;j++)
                {
                    for(l=ad[i][j];l!=-1;l=e[l].p)
                    {
                        x=e[l].x;
                        y=e[l].y;
                        sc=0;
                        for(ll=on[i][j][x][y];ll!=-1;ll=e[ll].p)
                        {
                            xx=e[ll].x;
                            yy=e[ll].y;
                            sc+=b[xx][yy];
                        }
                        dpt[x][y]=max(dpt[x][y],dp[i][j]+sc);
                    }
                }
            }
            memcpy(dp,dpt,sizeof dpt);
        }
        for(i=k=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                k=max(k,dp[i][j]);
        printf("%d\n",k);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<cstdio>

#include<cstring>

int n,d,m,ad[30][30],on[30][30][30][30],el;

int b[30][30],dp[30][30],dpt[30][30],t[11];

struct E

{

int x,y,p;

}e[5000000];

inline int inr(int x1,int y1,int x2,int y2)

{

return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=d*d;

}

inline int onl(int x1,int y1,int x2,int y2,int x3,int y3)

{

if(x1==x2) return x3==x1;

else if(x3==x1&&y3!=y1||x3==x2&&y3!=y2) return 0;

else return (y3-y1)*(x2-x1)==(y2-y1)*(x3-x1);

}

inline int max(int a,int b)

{

return a>b?a:b;

}

int main()

{

int i,j,k,l,ll,x,y,xx,yy,sc;

while(~scanf("%d%d%d",&n,&d,&m)&&n)

{

memset(ad,-1,sizeof ad);

memset(on,-1,sizeof on);

memset(t,-1,sizeof t);

el=0;

while(m--)

{

scanf("%d%d%d",&i,&j,&k);

e[el].x=i+5;

e[el].y=j+5;

e[el].p=t[k];

t[k]=el++;

}

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

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

for(k=0;k<n+10;k++)

for(l=0;l<n+10;l++)

if(inr(i,j,k,l))

{

e[el].x=k;

e[el].y=l;

e[el].p=ad[i][j];

ad[i][j]=el++;

}

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

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

for(ll=ad[i][j];ll!=-1;ll=e[ll].p)

{

int L,R,D,U;

k=e[ll].x;

l=e[ll].y;

if(i<k) L=i, R=k;

else L=k, R=i;

if(j<l) D=j, U=l;

else D=l, U=j;

for(x=L;x<=R;x++)

for(y=D;y<=U;y++)

if(onl(i,j,k,l,x,y))

{

e[el].x=x;

e[el].y=y;

e[el].p=on[i][j][k][l];

on[i][j][k][l]=el++;

}

memset(dp,0,sizeof dp);

for(k=1;k<11;k++)

{

memset(b,0,sizeof b);

memset(dpt,0,sizeof dpt);

for(l=t[k];l!=-1;l=e[l].p)

{

x=e[l].x;

y=e[l].y;

b[x][y]=1;

}

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

{

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

{

for(l=ad[i][j];l!=-1;l=e[l].p)

{

x=e[l].x;

y=e[l].y;

sc=0;

for(ll=on[i][j][x][y];ll!=-1;ll=e[ll].p)

{

xx=e[ll].x;

yy=e[ll].y;

sc+=b[xx][yy];

}

dpt[x][y]=max(dpt[x][y],dp[i][j]+sc);

}

memcpy(dp,dpt,sizeof dpt);

}

for(i=k=0;i<n+10;i++)

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

k=max(k,dp[i][j]);

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

}

return 0;

}

使用了同一种边表struct来存多种数据……虽然看上去很乱搞但自己清楚其实是合理的做法，能够AC实在是太好了。另外今天也去了渣打编程马拉松的北京初赛……地点竟然还是上次北大校赛的北交计算机培训中心。这次的待遇比北大校赛好多了，全程饮料零食供应，中午还一人一份M，只是我肠胃不好也没太敢吃。但如果就比赛本身来说，实在是不怎么样。题目本身说是大数据，其实数据一点也不大，就在百万级别而已。另外就是题目的描述和求解需求都不甚明确，还有前后矛盾的地方……问赛会人员也是越描越黑……最后下午3点的时候上传完解就提前走了。结果到门口竟然还被拦截采访。。。实在是太尴尬了。明显这种非IT公司办的比赛只是为了宣传+招聘，和技术实际是离天隔九丈了……但是来参加这种比赛的我又算什么……