【题目来源】
洛谷：P1879 [USACO06NOV] Corn Fields G - 洛谷
【题目描述】
农场主 John 新买了一块长方形的新牧场，这块牧场被划分成 \(M\) 行 \(N\) 列 (\(1≤M≤12,1≤N≤12\))，每一格都是一块正方形的土地。 John 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
【输入】
第一行：两个整数 \(M\) 和 \(N\)，用空格隔开。
第 \(2\) 到第 \(M+1\) 行：每行包含 \(N\) 个用空格隔开的整数，描述了每块土地的状态。第 \(i+1\) 行描述了第 \(i\) 行的土地，所有整数均为 \(0\) 或 \(1\) ，是 \(1\) 的话，表示这块土地足够肥沃，\(0\) 则表示这块土地不适合种草。
【输出】
一个整数，即牧场分配总方案数除以 \(100,000,000\) 的余数。
【输入样例】
2 3
1 1 1
0 1 0
【输出样例】
9
【算法标签】
《洛谷 P1879 Corn Fields》 #动态规划DP# #枚举# #状压DP# #USACO# #2006#
【代码详解】
// 参考AcWing 327的题解（董晓的题解无法AC）#include <bits/stdc++.h>
using namespace std;const int N = 14, M = 1 << 12, mod = 1e8; // 定义常量：最大行数N，状态数M，模数
int n, m; // 农田的行数n，列数m
int g[N]; // 记录每行土地是否肥沃（0肥沃，1贫瘠）
vector<int> state; // 存储所有合法的种植状态（不相邻）
vector<int> head[M]; // 存储每个状态可以转移到的其他状态
int f[N][M]; // DP数组，f[i][j]表示前i行种植且第i行状态为j的方案数// 检查状态是否合法（没有相邻的种植）
bool check(int state) {for (int i = 0; i < m; i++)if ((state >> i & 1) && (state >> (i + 1) & 1) // 检查是否有相邻的1return false;return true;
}int main() {cin >> n >> m; // 输入农田的行数和列数// 读取农田数据并预处理每行的贫瘠土地for (int i = 1; i <= n; i++)for (int j = 0; j < m; j++) {int t;cin >> t; // 输入土地状态（0肥沃，1贫瘠）g[i] += !t << j; // 将贫瘠土地的位置记录为1（使用位运算）}// 预处理所有合法的种植状态for (int i = 0; i < 1 << m; i++)if (check(i))state.push_back(i);// 预处理状态之间的转移关系for (int i = 0; i < state.size(); i++)for (int j = 0; j < state.size(); j++) {int a = state[i], b = state[j];if ((a & b) == 0) // 检查状态a和b是否可以相邻（不冲突）head[i].push_back(j);}// 初始化DP数组：第0行不种植的方案数为1f[0][0] = 1;// 动态规划过程for (int i = 1; i <= n + 1; i++) // 遍历每一行（多处理一行方便统计结果）for (int a = 0; a < state.size(); a++) // 遍历当前行的状态for (int b : head[a]) { // 遍历可以转移到状态a的上一行状态bif (g[i] & state[a]) continue; // 跳过在贫瘠土地上种植的状态f[i][a] = (f[i][a] + f[i - 1][b]) % mod; // 状态转移}// 输出结果：前n+1行种植且第n+1行不种植的方案数（即前n行的总方案数）cout << f[n + 1][0] << endl;return 0;
}
【运行结果】
2 3
1 1 1
0 1 0
9