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

## 前排警告 ### 这是写给刚学的我看的，大佬请自动忽略 人生第一道状压$dp$ ~~互不侵犯是学术交流过的~~ 本蒟蒻今天在机房听到状压$dp$，感觉很高大上……其实就是位运算高大上一点 #### 解释一下位运算： & 给个例子 $0110101+1010011=0010001$，返回值为$17$ $n<<k$ 将$n$左移$k$位，相当于给$n$乘上$2^k$ $n>>k$ 将$n$右移$k$位，相当于给$n$除以$2^k$后向下取整 #### 解释一下状压$dp$： 它的基本思想就是用二进制来优美地暴力枚举出现的方案， 若二进制下第$i$位有赋值$1$，则一行的第$i$列有放牛 那么$f[i][j]$表示在前$i$行中（包括$i$）在$j$个状态下的最大方案数 易得$f[i][j]=(f[i][j]+f[i-1][k])\ mod\ p$（$p=10^9$，$j$是第$i$行的状态，$k$是第$i-1$行的状态） 所以我们还要再预处理一下，$g[i]$表示第$i$个状态是否存在，判断条件是 $g[i]=$ $!(i$&$(i>>1))!(i$&$(i<<1))$ 目标状态：$f[n][i]$全部相加 $Code \ Below:$ ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int p=100000000; ll f[13][1<<12],n,m; ll g[1<<12],h[1<<12],a[13][13]; ll F[13]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) F[i]=(F[i]<<1)+a[i][j]; for(int i=0;i<(1<<m);i++){ if(!(i&(i>>1))&&!(i&(i<<1))){ g[i]=1; if((i&F[1])==i) f[1][i]=1; } } for(int x=2;x<=n;x++) for(int j=0;j<(1<<m);j++) if(((j&F[x-1])==j)&&g[j]) for(int k=0;k<(1<<m);k++) if(((k&F[x])==k)&&!(j&k)&&g[k]){ f[x][k]=(f[x][k]+f[x-1][j])%p; } int ans=0; for(int i=0;i<(1<<m);i++) ans=(ans+f[n][i])%p; printf("%d\n",ans); return 0; } ```