题目链接
题意：Farmer John 放牧cow，有些草地上的草是不能吃的，用0表示，然后规定两头牛不能相邻放牧。问你有多少种放牧方法。
状态压缩dp其实就是用二进制来表示所有的状态，比如这题， 我们在某一行可以这样取0 1 0 1 1 0 1，用1代表取了，0代表没取，因为这点，它的数据量也限制在20以内，所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据，所有状态的总数必然很庞大，而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况，我们可以用二进制的一位来表示，0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45，如果我们想要枚举6个点的所有状态，我们只需要从0到2^6取其二进制就可以了，并不会重复或是多余。
然后关于这题，题目要求不相邻，也就是说每个状态中不能有两个1相邻，代码中我用了checkself()函数判断。还有，有些地方是非法的，我在输入的时候将非法的状态保存了，一行只占一个整数，只需要判断某状态中只要有个一位和非法状态总的一位都为1，这个状态必然非法，这里我用了check()函数。
我们检测完了状态的合法性，接下来就是状态转移的问题了。对于当前行的合法状态，到这个状态的方法数目一定是前一行与它不冲突（也就是没有行之间相邻的点）的方法数之和（记得mod）。这样求出到最后一行所有状态的方法数，求其和，然后取余，这就是我们要的结果。
#include <stdio.h> #include <string.h> #define MOD 100000000 #define maxn 13 int dp[maxn][1<<maxn]; //每个状态可以放牧方法的总数 int n, m; int sta[maxn]; //能不能放牧的状态 bool check(int x, int y) //检查同列有没有相邻的或者x的状态是否可以存在 { if (x&y) return false; return true; } bool checkself(int x) //检查同行有没有相邻的 { if (x&(x<<1)) return false; return true; } int getresult() { int num = 1<<m; for (int i = 0; i < num; i++) { if (check(i, sta[1]) && checkself(i)) dp[1][i] = 1; } for (int i = 2; i <= n; i++) { for (int j = 0; j < num; j++) { if (!check(j, sta[i])) //sta[i]表示i行不能存在的状态 continue; for (int k = 0; k < num; k++) { if (check(k, j) && checkself(j) && checkself(k)) dp[i][j] += (dp[i-1][k]%MOD); } } } int ans = 0; for (int i = 0; i < num; i++) { ans += (dp[n][i]%MOD); } return ans%MOD; } int main() { int t; while (scanf("%d %d", &n, &m) != EOF) { memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &t); if (!t) { sta[i] += (1<<(m-j)); //这里对不能出现的状态做标记 } } } printf("%d\n", getresult()); } return 0; }
![[UVA1364 | POJ | NC]Knights of the Round Table | Tarjan 求点双 | 二分图 | 综合图论](https://ucc.alicdn.com/pic/developer-ecology/d14f6beadb884a3cb2d6c8a10981c6cd.png?x-oss-process=image/resize,h_160,m_lfit)