二进制枚举、状压dp

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



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



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



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



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



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



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



    亚英雄的方法？

输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。

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

3 3
1 1 1
0 1 1
1 0 0

24

解题思路

题目给出的可以允许二进制的枚举范围。地图题并且合计方法数，考虑状压dp。 代表第i行安放情况为j的方法数。j用二进制表示。
那么对于二进制枚举来说，地图和安放士兵也有关系，而二进制状压中，用位运算更优先，那么吧地图存放在一个int的二进制串中。
对于枚举的本行状态，首先和地图不能冲突，第二不能相邻安放士兵，第三枚举上一行的情况，进行状态转移。注意上下某一列不能同时为1。

那么直接三重循环即可。时间复杂度

Code

#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;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int MOD = 100000000;
inline ll read() { ll s = 0, w = 1; char ch = getchar();    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int N = 13;
ll mp[N], dp[N][1 << N];
int n, m;

int main() {
    while (~scanf("%d %d", &n, &m)) {
        memset(mp, 0, sizeof(mp));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                int x = read();
                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 & mp[i]) != j)    continue; //j为1的mp[i]这一位为0，不能放士兵
                if (j & (j >> 1))    continue; // 存在相邻士兵情况
                for (int 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 (int i = 0; i < 1 << m; ++i)
            (ans += dp[n][i]) %= MOD;
        printf("%lld\n", ans);
    }
    return 0;
}