学步园

第一道状态压缩DP

参考acCry大牛的题解

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXS = 65535,MAXN = 15 , mod = 100000000;
int dp[MAXN][MAXS],line[MAXS],map[MAXN],m,n,s;

int init()///初始化
{
    memset(dp,0,sizeof(dp));
    s=0;
    memset(line,0,sizeof(line));
}

bool ck(int x,int y) ///check line
{
    x|=y;
    if((x<<1)&x) return 0;
    else return 1;
}

void fl()///第一次处理
{
    for(int i=0;i<(1<<n);i++)///找行的所有可能性 存在line中
        if(ck(line[s],i))
            line[s++]|=i;

    for(int i=0;i<s;i++)///初始化dp[0]
    {
        if(!(line[i]&map[0]))
            dp[0][i]= 1;
    }
}

int main()
{
    while(scanf("%d%d",&m,&n)==2)
    {
        init();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                int tmp;
                scanf("%d",&tmp);
                if(!tmp) map[i]|=1<<j; ///取反存储map
            }
        }
        fl();
        int cnt=0;
        for(int i=1;i<m;i++)
        {
            for(int j=0;j<s;j++)
            {
                if(line[s]&map[i-1])continue;///确保本行不与map冲突
                for(int k=0;k<s;k++)
                {
                    if((line[k]&line[j])||(line[k]&map[i])) continue;///确保下一行不与本行&&map冲突
                    dp[i][k]=(dp[i][k]+dp[i-1][j])%mod;///**状态转移为向下加
                }
            }
        }
        for(int i=0;i<s;i++)
            cnt=(cnt+dp[m-1][i])%mod;///**记得最后也要取余
        printf("%d\n",cnt);
    }
    return 0;
}