欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.7.26第二场T1题解

程序员文章站 2022-06-02 12:33:18
...

状压dp。

设dp(i,j,s)表示

2018.7.26第二场T1题解

(对绿点进行状压,1表示有障碍,即有小伙伴或已被标枪攻击。否则为0)。

转移时考虑(i,j)上的标枪是横的还是竖的,分别进行转移即可。

若(i,j)上已有障碍,则转移到(i,j+1,若j=m则转移到(i+1,j)。

时间复杂度O(NM2M)

代码:

#include <stdio.h>
int dp[22][20][33010],md=10086;
bool za[22][20];
int main()
{
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
    {
        while(1)
        {
            int a;
            scanf("%d",&a);
            if(a==0)
                break;
            za[i][a-1]=true;
        }
    }
    for(int i=N;i>=0;i--)
    {
        for(int j=M;j>=0;j--)
        {
            for(int s=0;s<(1<<M);s++)
            {
                if(i==N)
                {
                    if(s==0)
                        dp[i][j][s]=1;
                    else
                        dp[i][j][s]=0;
                    continue;
                }
                if(j==M)
                {
                    dp[i][j][s]=dp[i+1][0][s];
                    continue;
                }
                if(j+1<M)
                {
                    if(!(s&(1<<(M-j-1)))&&!(s&(1<<(M-j-2)))&&!za[i][j]&&!za[i][j+1])
                        dp[i][j][s]=(dp[i][j][s]+dp[i][j+2][s])%md;
                }
                if(!(s&(1<<(M-j-1)))&&!za[i][j])
                {
                    if(!za[i+1][j])
                        dp[i][j][s]=(dp[i][j][s]+dp[i][j+1][s|(1<<(M-j-1))])%md;
                }
                else
                {
                    if(s&(1<<(M-j-1)))
                        dp[i][j][s]=dp[i][j+1][s^(1<<(M-j-1))];
                    else
                        dp[i][j][s]=dp[i][j+1][s];
                }
            }
        }
    }
    printf("%d",dp[0][0][0]);
    return 0;
}
相关标签: 题解