下面有别人的题解报告，并且不止这一个状态压缩题的哦····
http://blog.csdn.net/accry/article/details/6607703
下面是我的代码，代码很挫，绝对有很大的优化的空间····
#include <cstdio>
#include <cstring>
int dp[][( << ) + ];
//检查一行的奶牛放置情形是否合理
//即是否有相邻的两个1，没有返回true
bool checkHori(int state)
{
if(!(state & (state << )) ) return true;
else return false;
} //检查竖直方向的奶牛放置情形是否合理
//即是否竖直方向有相同的1
bool checkVert(int a,int b)
{
if(!(a&b)) return true;
else return false;
} //看该位置是否是肥沃的土地
//关系式自己推出来
bool checkPos(int map,int state)
{
if( (map| state) == map) return true;
else return false ;
} //该算法时间复杂度很高，为O(m*2^(2*n))
//最坏情况下为O(12*2^24),10^8左右,一定是可以改进的
int main()
{
freopen("in.cpp","r",stdin);
int m,n;
scanf("%d%d",&m,&n);
memset(dp,,sizeof(dp));
dp[][] = ;
int x=;
for(int i=; i<=m; ++i)
{
int t,tmp=,map =; //map用来记录第i行土地的土壤状态
for(int d=; d<n ; ++d)
{
scanf("%d",&t);
map += t*tmp;
tmp *=;
}
x =-x;
for(int j=; j< ( << n); ++j)
dp[x][j] = ; //滚动数组，用时间换空间
for(int j=; j< ( << n); ++j)
{
for(int k=; k < ( << n); ++k)
{
if( checkHori(k) && checkPos(map,k) && (i == || checkVert(k,j) ) )
dp[x][k] += dp[-x][j];
}
}
}
int ans=;
for(int i=; i< ( << n); ++i)
{
ans += (dp[x][i] % );
ans %= ;
}
printf("%d\n",ans);
return ;
}
通过计算得出，当n = 12时，2^12 = 4096，而一行能成功放置的方法数仅为377，
由此可先预处理，离散化存储，极大地降低复杂度。新的算法的复杂度最坏情况下为12*377*377，大概为10^6的复杂度。
#include <cstdio>
#include <cstring>
int dp[][];
int st[];
//检查一行的奶牛放置情形是否合理
//即是否有相邻的两个1，没有返回true
bool checkHori(int state)
{
if(!(state & (state << )) ) return true;
else return false;
} //检查竖直方向的奶牛放置情形是否合理
//即是否竖直方向有相同的1
bool checkVert(int a,int b)
{
if(!(a&b)) return true;
else return false;
} //看该位置是否是肥沃的土地
//关系式自己推出来
bool checkPos(int map,int state)
{
if( (map| state) == map) return true;
else return false ;
} int init(int n)
{
int num=;
for( int i=; i<(<<n); ++i )
{
if(checkHori(i))
{
st[num++] = i;
}
}
return num;
}
int main()
{
// freopen("in.cpp","r",stdin);
int m,n;
scanf("%d%d",&m,&n);
int num=init(n);
memset(dp,,sizeof(dp));
dp[][] = ;
int x=;
for(int i=; i<=m; ++i)
{
int t,tmp=,map =; //map用来记录第i行土地的土壤状态
for(int d=; d<n ; ++d)
{
scanf("%d",&t);
map += t*tmp;
tmp *=;
}
x =-x;
for(int j=; j< num; ++j)
dp[x][j] = ; //滚动数组，用时间换空间
for(int j=; j< num; ++j)
{
for(int k=; k < num; ++k)
{
if(checkPos(map,st[k]) && (i == || checkVert(st[k],st[j]) ) )
dp[x][k] += dp[-x][j];
}
}
}
int ans=;
for(int i=; i< num; ++i)
{
ans += (dp[x][i] % );
ans %= ;
}
printf("%d\n",ans);
return ;
}