抹茶柚子冰1. 状压DP实战：Corn Fields问题解析
今天我们来深入探讨一个经典的状压DP问题——Corn Fields（玉米地种植规划）。这个问题在各类算法竞赛中频繁出现，是理解状态压缩动态规划的绝佳案例。我曾在多次比赛中遇到过这个问题的变种，也指导过不少学生解决类似的题目，下面就把我的实战经验完整分享给大家。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 问题建模与状态设计
2.1 问题重述
农场主John新购买了一块M×N的矩形牧场（1≤M,N≤12），计划种植玉米。牧场被划分为M行N列的小方格，有些方格因为贫瘠无法种植。种植时需要满足：
- 相邻的方格（上下左右）不能同时种植
- 只能在肥沃的方格上种植
我们需要计算所有满足条件的种植方案数，结果对1e8取模。
2.2 状态表示的精髓
状压DP的核心在于用二进制数表示一行的种植状态。对于N列的土地，我们用N位二进制数表示，1表示种植，0表示不种植。例如对于5列的土地：
- 10101 表示第1、3、5列种植
- 00100 表示仅第3列种植
关键点：状态合法性需要满足两个条件：
- 种植位置必须对应土地肥沃（输入数据决定）
- 同一状态内不能有相邻的1（即x&(x<<1)==0）
3. 预处理与状态转移
3.1 预处理合法行状态
我们先预处理出所有自身合法的状态（无相邻1）：
cpp复制vector<int> valid_states;
for(int mask=0; mask<(1<<n); ++mask){
if(!(mask & (mask<<1))){ // 检查相邻位
valid_states.push_back(mask);
}
}
3.2 土地肥沃状态处理
用fertile[i]表示第i行的土地肥沃状态，也是一个二进制数。例如输入为：
code复制1 1 1
0 1 0
则fertile[1] = 0b111，fertile[2] = 0b010
3.3 状态转移方程设计
定义dp[i][S]：处理到第i行，第i行状态为S时的方案数
转移方程：
dp[i][S] = Σ dp[i-1][T]
其中：
- S是第i行的合法状态
- T是第i-1行的合法状态
- S与T不冲突