UESTC 882 冬马党 –状压DP

定义：dp[i][j]为状态为j时，第i行符合条件的状态数

转移方程：dp[i][j] += dp[i-1][t]   //t为上一行状态，与当前行不冲突。

从第一行开始向下枚举，每次枚举当前行的状态和上一行的状态，如果不相邻或者未被地雷占据并且两行的关系是合法的，则加上方法数。

最后res = SUM(dp[n][s]) (s=0~S,为最后一行的状态)

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 100000000//dp[i][j]:状态为j时，第i行符合条件的状态数
int wei[];
int a[];
int dp[][];int checkadj(int state)
{
    if(state & (state<<))   //相邻
        return ;
    return ;
}int checkplace(int state,int i)
{
    if(state & wei[i])     //被地雷占据
        return ;
    return ;
}int main()
{
    int n,m,i,j,k,state;
    scanf("%d%d",&n,&m);
    memset(wei,,sizeof(wei));
    memset(dp,,sizeof(dp));
    for(i=;i<=n;i++)
    {
        for(j=;j<=m;j++)
        {
            scanf("%d",&state);
            if(!state)
                wei[i] += (<<(m-j));  //被地雷占据赋为1
        }
    }
    int Fst = <<m;
    k = ;
    for(state=;state<Fst;state++)   //第一行
    {
        if(checkadj(state))
        {
            a[k++] = state;
            if(checkplace(state,))
                dp[][k-] = ;
        }
    }
    for(i=;i<=n;i++)
    {
        for(j=;j<k;j++)   //枚举上一行
        {
            if(!checkplace(a[j],i-))
                continue;
            for(state=;state<k;state++)  //枚举这一行
            {
                if(!checkplace(a[state],i) || (a[j] & a[state]))
                    continue;
                dp[i][state] = (dp[i][state] + dp[i-][j])%N;
            }
        }
    }
    int res = ;
    for(i=;i<k;i++)
        res = (res + dp[n][i])%N;
    printf("%d\n",res);
    return ;
}