【每日一题】6月3日德玛西亚万岁

德玛西亚万岁

https://ac.nowcoder.com/acm/problem/15034

题意

德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。

这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。

有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。

结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土

地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标

记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他

们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西

亚英雄的方法？

输入描述

输入包含多组测试数据；

每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 )，之间用空格隔开；

接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。

输出描述

输出一个整数n代表安排应用的方法。（答案取膜100000000）

解析

状压dp二进制枚举，数据范围 $n，m<=12$ 是允许二进制枚举的范围， dp[i][j]代表第i行安放情况为j的方法数。j用二进制表示。

注意一下为0的地方dp到的时候直接退出还有出现相邻的时候

直接看代码吧，在代码里会写一下注释

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 100000000;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int MAXN=13;
ll mp[MAXN];
ll dp[MAXN][1<<MAXN];

int main(void){
    int n,m;
    while(cin>>n>>m){
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                ll x;
                cin>>x;                      //将每一行的01用二进制储存 比如011就是3
                mp[i]=(mp[i]<<1)+x;
            }
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(ll i=1;i<=n;++i){
            for(ll j=0;j< 1<<m;++j){
                if((j&mp[i])!=j) continue;              //j为1的mp[i]这一位为0，不能放士兵 
                if(j&(j>>1)) continue;                // 存在相邻士兵情况
                for(ll k=0;k< 1<<m ;++k){
                    if(k&j) continue;
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
                }
            }
        }
        ll ans=0;
        for(ll i=0;i< 1<<m;++i){
            (ans+=dp[n][i])%=MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}