Description

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

Solution

补题向，一点进来就看见状压dp关键词，看数据范围 确实也是状压dp
考虑几种情况就可以了：

  • 列不能连续1, 通过枚举上下行的状态， 为 true 的话就是有连续的1
  • 行不能连续1，通过检验 为 true 的话就是有连续的1
  • 和原图的0不能放，通过记录每一行的二进制状态，与当前状态 有 的话就是不相矛盾

注意多组数据！！还有数组记得开够！！

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 5e5 + 5;
typedef long long ll;

int mp[105];
int n, m;
int dp[105][105];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  while(cin >> n >> m) {
    memset(mp, 0, sizeof(mp));
    for(int i = 1; i <= n; i++) {
      for(int j = 0; j < m; j++) {
        int x;
        cin >> x;
        mp[i] = (mp[i] << 1) + x;
      }
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
      for(int j = 0; j < (1 << m); j++) {
        if(j & (j >> 1)) continue; // 有连续的1
        if((j & mp[i]) != j) continue; // 跟原图矛盾了
        for(int k = 0; k < (1 << m); k++) { // 枚举上一行情况
          if(j & k) continue;
          dp[i][j] += dp[i - 1][k];
          dp[i][j] %= mod;
        }
      }
    }
    ll ans = 0;
    for(int i = 0; i < (1 << m); i++) {
      ans += dp[n][i];
      ans %= mod;
    }
    cout << ans << "\n";
  }
  return 0; 
}