【[USACO06NOV]Corn Fields G】【状压DP】

• [USACO06NOV]Corn Fields G
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
• 思路讲解
• 题解代码

农场主 J o h n rm John John 新买了一块长方形的新牧场，这块牧场被划分成 M M M 行 N N N 列 ( 1 ≤ M ≤ 12 ; 1 ≤ N ≤ 12 ) (1 le M le 12; 1 le N le 12) (1≤M≤12;1≤N≤12)，每一格都是一块正方形的土地。 J o h n rm John John 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 J o h n rm John John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

J o h n rm John John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

第一行：两个整数 M M M 和 N N N，用空格隔开。

第 2 2 2 到第 M + 1 M+1 M+1 行：每行包含 N N N 个用空格隔开的整数，描述了每块土地的状态。第 i + 1 i+1 i+1 行描述了第 i i i 行的土地，所有整数均为 0 0 0 或 1 1 1 ，是 1 1 1 的话，表示这块土地足够肥沃， 0 0 0 则表示这块土地不适合种草。

一个整数，即牧场分配总方案数除以 100 , 000 , 000 100,000,000 100,000,000 的余数。

2 3
1 1 1
0 1 0

9

首先用位运算 | 将每一行的信息存进mp里； 对第一行单独初始化，后依次枚举本行状态和上一行的状态，枚举每种状态时记得除去不可行解

采用位运算判断无疑是最快的

j & j-1 可以快速判断是否有两个以上连续的1；

( mp[i] | l ) == mp[i] ; 可以判断是否在地图上是 0 的位置种草了。

mp[i] 中有一位是 1 ，那么无论 i ( i 为当前行状态）的这一位是什么都不会改变;

mp[i]中某位为 0 时，如果 i 状态的当前位置为1（种草）则会改变mp[i]的值；

#include 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair pii;
typedef vector vi;
typedef vector vll;
typedef vector> vpii;
#define all(a) a.begin(), a.end()
#define nl 'n'
#define debug() cout << "debug:"
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const int mod = 1e9;
int mp[105] = {0};      //mp存储地图情况
int dp[13][1 << 12];    //dp枚举每一种状况
void solve(){
    int n, m;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++){
            int x;
            cin >> x;
            mp[i] |= (x << j); //记录地图信息
            // 1 1 1 记录为 mp[1] = 7;
            // 0 1 0 记录为 mp[2] = 2;
        }
    // for (int i = 1;i<=m;i++){
    //     cout << mp[i] << " ";
    // }
    for (int l = 0; l < (1 << n); l++){
        if ((l & (l >> 1)))//不能相邻
            continue;
        if ((mp[1] | l) != mp[1])//不能种草
            continue;
        dp[1][l] = 1;
    } //初始化第一行的情况
    for (int i = 2; i <= m; i++){
        for (int j = 0; j < (1 << n); j++){ //当前行
            int flag = 1;
            if ((j & (j >> 1)))
                continue; //判断当前行是否有相邻的情况
            if ((mp[i] | j) != mp[i])
                continue; //判断是否在0的位置种草了
            for (int l = 0; l < (1 << n); l++){
                if ((l & (l >> 1)))
                    continue; //判断上一行是否有相邻的情况
                if ((mp[i - 1] | l) != mp[i - 1])
                    continue;
                if (l & j)
                    continue; //判断此行和上一行是否相邻
                dp[i][j] += dp[i - 1][l];
                dp[i][j] %= mod;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < (1 << n); i++){
        sum += dp[m][i];
        sum %= mod;
    }
    cout << sum << nl;
}
int main(){
    // ios::sync_with_stdio(0);
    // freopen("in", "r", stdin);
    int t = 1;
    // cin>>t;
    while (t--)
        solve();
    return 0;
}