其实没什么好说的，就是在棋盘上的。
题目
P2915 [USACO08NOV] Mixed Up Cows G(混入的)
这个应该算是旅行商问题。
解法
状态定义:
\(dp_{i,state}\) 表示选择状态为 \(state\)，以第 \(i\) 头奶牛为结尾的方案数。
状态转移方程式
\[dp_{j,s|(1<<j)} = \sum dp_{i,s}
\]
哦对了！不要忘记了特殊条件！
相邻奶牛的编号之差均超过K
代码
戳我喵~
int a[17];
lint dp[17][(1 << 16) + 10];int main() {int n = re, k = re;for (int i = 0; i < n; i++) a[i] = re;for (int i = 0; i < n; i++) dp[i][1 << i] = 1;for (int s = 0; s < (1 << n); s++) {for (int i = 0; i < n; i++) {if ((s >> i) & 1) {for (int j = 0; j < n; j++) {if (!((s >> j) & 1) && abs(a[j] - a[i]) > k) {dp[j][s | (1 << j)] += dp[i][s];}}}}}lint ans = 0;for (int i = 0; i < n; i++) ans += dp[i][(1 << n) - 1];wr(ans), endl;
}
P1879 [USACO06NOV] Corn Fields G
这题太经典了！
解法
先看数据范围：\(1 \le n,m \le 12\)
可以状压！
我们注意力惊人，发现了只有与它相邻的行与列才有关，所以我们考虑压缩一行的状态。
所以我们定义 \(dp_{i,j}\) 表示第 \(i\) 行，采用了第 \(j\) 个合法状态时的方案总数。
可是合法状态怎么统计呢？
我们可以在预处理阶段处理这合法状态。
合法状态即满足题目的条件，即不能有两块奶牛所在的草地相邻。
我们只需要判断 i & (i >> 1) 是否为 \(0\)，如果为 \(0\)，那么它就是中意的方案。
最后的 \(DP\) 还算简单，看代码就能理解。
状态转移方程式：
\[dp_{i,j} = \sum dp_{i - 1,k}
\]
代码
戳我喵
```plaintext
lint f[20], dp[20][(1 << 15) + 10]; //f是用来记录草地状态的
int n, m;int main() {IAKIOI;n = re, m = re;for (int i = 1; i <= n; i++) for (int j = 0, x; j < m; j++) {x = re;if (x) f[i] |= (1 << j);}vector<int> v;for (int i = 0; i < (1 << m); i++) if ((i & (i >> 1)) == 0) v.push_back(i);dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < v.size(); j++) {if ((v[j] & f[i]) == v[j]) {for (int k = 0; k < v.size(); k++) {if (!(v[j] & v[k])) {dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod; }}}}}lint ans = 0;for (int i = 0; i < v.size(); i++) ans = (ans + dp[n][i]) % mod;wr(ans), endl;
}
</details>