topcoder SRM 573 Div2 1000

00:00/00:00

1000:WolfPackDivTwo

题意:

你有一些点,每次你可以用一步的代价走到上下左右四个格子中的一个,然后问你走m步以后,所有点在同一个点上的种类数。。。

分析:

我们可以先dp出相对走到一个点的种类数,最后枚举终点就可以找到答案。。。

代码:

int num;
int dp[200][200][60];
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,-1,1};
int WolfPackDivTwo::calc(vector  x, vector  y, int m) 
{
    int ret=0;
    num=x.size();
    memset(dp,0,sizeof(dp));
    dp[55][55][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=4;j<=106;j++)
            for(int k=4;k<=106;k++)
                for(int l=1;l<=4;l++)
                    dp[j][k][i]=(dp[j][k][i]+dp[j+dx[l]][k+dy[l]][i-1])%mod;
    for(int i=-m;i<=50+m;i++)
        for(int j=-m;j<=50+m;j++)
        {
            LL ans=1;
            for(int k=0;k<num;k++)
            {
                if(55-x[k]+i<0||55-y[k]+j<0){ans=0;break;}
                ans=ans*dp[55-x[k]+i][55-y[k]+j][m]%mod;
            }
            ret=(ret+ans)%mod;
        }
    return ret;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注