题解 P1879 【[USACO06NOV]玉米田Corn Fields】

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述-->[p1879 [USACO06NOV]玉米田Corn Fields](https://www.luogu.org/problemnew/show/P1879) ### 分析 **下面的$n,m$为$n$行$m$列,与题目描述不符.** 难得做起了状压DP的题 $f[i]$代表第$i$行的状态.就是输入的状态,这个东西的话就直接算就好了. $$(f[i]<<=1)|=x$$ 初始化：$dp[0][0]=1$ 那么我们需要枚举每一行,再枚举状态$j$判断当前行的状态$f[i]$是否会包含状态$j$,即合法与否. 判断不能有相临的话,直接写一个函数即可  这里就不多解释了. 然后在枚举上一行状态$k$是否与当前状态$j$不相邻.即上下＆起来为0。 (这就涉及到了＆的性质,两边为$True$才为$True$) $$ans=\sum_{i=0}^{(1<<m)-1}f[n][i]$$ 时间复杂度$O(n \times 2^{m+1})$ ``代码`` ```c++ #include<cstdio> #include<cctype> #define mod 100000000 #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int res[15][15],f[18],n,m,dp[18][1<<15],ans; inline bool ok(int state) { return ((state&(state>>1))==0 and (state&(state<<1))==0); } int main() { in(n),in(m); for(R int i=1;i<=n;i++) for(R int j=1,x;j<=m;j++) { in(x); (f[i]<<=1)|=x; } int state=(1<<m)-1; dp[0][0]=1; for(R int i=1;i<=n;i++) for(R int j=0;j<=state;j++) if(ok(j) and (f[i]&j)==j) for(R int k=0;k<=state;k++) if((k&j)==0) (dp[i][j]+=dp[i-1][k])%=mod; for(R int i=0;i<=state;i++) (ans+=dp[n][i])%=mod; printf("%d",ans%mod); } ```