每日一题 德玛西亚万岁 (状压dp)

一.题意

德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？

二.题解

首先 表示第 i 行状态为 j 的合法方案数，然后考虑一行一行枚举下去，当前行的合法方案由上一行的合法方案推出，当然什么都不放也是一种方案，所以初始化 。

枚举时需要注意当前状态是否符合地图，即判断是否出现当前状态1地图0的情况：mp[ i ]& j 是否等于j。

特别需要注意的是不能相邻同时放，所以考虑行列连续的情况。

1. 行连续 : 判断 j & (j>>1) 是否为 1 ，意思是把当前状态上的 1 往左移，判断是否有重叠，即判断行连续。
2. 列连续 : 判断 j & k 是否为 1 ， 意思是判断当前状态 j 和上一行的状态 k 是否有重叠。

三.代码:

#include<bits/stdc++.h>
#define pb push_back
#define ld long double
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;
const int mo=1e8;

ll n,m;
ll mp[15];
ll dp[15][1<<15];

int main(){
    io; 
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            mp[i]=0;
            for(int j=1;j<=m;j++){
                ll x; cin>>x;
                mp[i]=(mp[i]<<1)+x;
            }
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<(1<<m);j++){
                if(j&(j>>1)) continue;
                if((j&mp[i])!=j) continue;
                for(int k=0;k<(1<<m);k++){
                    if(k&j) continue;
                    dp[i][j]+=dp[i-1][k]; dp[i][j]%=mo;
                }
            }
        }
        ll ans=0;
        for(int i=0;i<(1<<m);i++) ans=(ans+dp[n][i])%mo;
        cout<<ans<<endl;
    }
    return 0;
}