bzoj1725： [Usaco2006 Nov]Corn Fields牧场的安排(状压dfs)

/*
我才不要写状压dp呢！！
状压dfs
对于每一行dfs一次。顺便记录这一行的状态能否对下一行的状态产生贡献。
*/
#include<bits/stdc++.h> #define N 100000
#define S 30
#define mod 100000000 using namespace std;
int m,n,ans;
int f[S][N],a[S]; inline int read()
{

int x=,f=;char c=getchar();<br/>
while(c&gt;&#39;&#39;||c&lt;&#39;&#39;){if(c==&#39;-&#39;)f=-;c=getchar();}<br/>
while(c&gt;=&#39;&#39;&amp;&amp;c&lt;=&#39;&#39;){x=x*+c-&#39;&#39;;c=getchar();}<br/>
return x*f;<br/>

} void dfs(int x,int y,int sta,int nxt)//nxt是下行状态
{

if(y&gt;=n)<br/>
{<br/>
    f[x+][nxt]+=f[x][sta];<br/>
    f[x+][nxt]%=mod;<br/>
    return;<br/>
}<br/>
dfs(x,y+,sta,nxt);//不放<br/>
if(!(sta&amp;(&lt;&lt;y))) dfs(x,y+,sta,nxt|(&lt;&lt;y));//保证左右，和下面不相邻<br/>

} int main()
{

int x;<br/>
m=read();n=read();<br/>
for(int i=;i&lt;=m;i++) for(int j=;j&lt;n;j++)<br/>
{<br/>
    x=read();<br/>
    if(x==) a[i]=a[i]|(&lt;&lt;j);<br/>
}f[][a[]]=;//初始，第一行，不放，方案数为1 

for(int i=;i<=m;i++) for(int j=a[i];j<(<<n);j++)

  if(f[i][j]) dfs(i,,j,a[i+]);//如果当前航这个状态合法，就从这个状态dfs<br/>
for(int i=;i&lt;(&lt;&lt;n);i++)<br/>
ans+=f[m+][i],ans%=mod;<br/>
printf(&#34;%d\n&#34;,ans);<br/>
return ;<br/>

}