简述

　　那个提示里说的好麻烦好麻烦啊，最后竟然推出辣么一坨式子，我看着就眼晕。 　　这个其实是插头 DP 入门题。 　　根据 will7101 大爷的说法，你的状压记录的是上面一行的每一个位置是否有一个插头插下来。 　　显然要先暴力枚举相邻两行的状态，然后写个 check 函数，如果 check 成功，进行转移。 　　问题是 check 怎么写。 　　搞了半天才搞出来，最后我是这么写的： 　　假设上一行的状态是 a ，这一行的状态是b，首先对于 a 的每个二进制位，如果是1，就检查 b 的这一位是不是1，如果是，就返回 false ，否则把对应的 b 位置赋成1。 　　最后扫一遍b，如果连续的 0 有奇数个，就返回false。 　　如果上述检查都通过了，就返回 true 。

代码

//插头DP #include <cstdio> #include <algorithm> #include <bitset> #include <iostream> #define mod 1000000007 using namespace std; int f[1005][40], N, M; bool check(int x, int y) { bitset<10> a(x), b(y); int i; for(i=0;i<M;i++)if(a[i]==1 and b[i]==1)return false; for(i=0;i<M;i++)if(a[i]==1)b[i]=1; for(i=0;i<M;i++) { if(b[i]==1)continue; if(b[i]==0 and (i==M-1 or b[i+1]==1))return false; else i++; } return true; } int main() { int i, j, k, ans=0; f[0][0]=1; scanf("%d%d",&N,&M); for(i=1;i<=N;i++) for(j=0;j<(1<<M);j++) for(k=0;k<(1<<M);k++) if(check(j,k))f[i][k]=(f[i][k]+f[i-1][j])%mod; printf("%d",f[N][0]); return 0; }