Corn Fields poj3254

　　　　题目大意：给你一个n*m的地，每一块地可以种或不种，两块种过的地不能挨着，可以一块都不种，问所有的种地方案数。

　　　　注释：读入用0和1，1<=n,m<=12.

　　　　　　想法：这题和炮兵阵地特别像，比炮兵更简单。我们再度入的时候直接处理出当前行的地的不可种的情况。预处理出一行如果都能种的话所可能的方案数。此处需要满足的就是两块地不能挨着，通过打表我们可以发现这种情况最多只有377种情况(我们附上打表用的程序)

#include 
     
      #include 
      
       #include 
       
        using namespace std;bool check(int x)//判断当前状态是否可行{	if(x&(x<<1)) return false;	return true;}int cnt;void before(int mid)//处理所有状态{	for(int i=0;i<(1<
        
         > n;	before(n);	printf("%d\n",cnt);//输出所有可行状态数	return 0;}
        
       
      
     

 　　　　　　然后，我们先预处理出第一行，怎么处理呢？其实map是0的情况，也就是读入数据的反码。我们对于一个状态只需要通过&上map对应的下标就可以判断当前数据是否合法。如果合法，dp[1][i]就是1。其中，dp[i][j]表示第 i 行状态为 j ，前 i 行能填充的方案数。转移时，我们通过外层松弛行数，内层枚举所有状态，用&判断即可。

　　　　最后，附上丑陋的代码... ...

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mod 1000000000using namespace std;int dp[15][380];int map[15];//存储的是反码int str[380];//存储所有状态// int sum[350];int cnt;//状态数目bool check(int x)//判断当前状态是否可行{	if(x&(x<<1)) return false;	return true;}// int getSum(int x)// {// 	int ans=0;// 	while(x>0)// 	{// 		if(x&1) ans++;// 		x>>=1;// 	}// 	return ans;// }void before(int mid)//预处理所有状态{	for(int i=0;i<(1<
         
          > n >> m;	int a;	for(int i=1;i<=n;i++)	{		for(int j=1;j<=m;j++)		{			scanf("%d", &a);			if(a==0) map[i]|=(1<<(j-1));//运用|运算的性质来构造反码		}	}	before(m);//预处理	// cout << "cnt = " << cnt << endl;	for(int i=1;i<=cnt;i++)	{		if(!(str[i] & map[1]))		{			dp[1][i]=1;		}	}	// for(int i=1;i<=n;i++) printf("%d ",map[i]);	// puts("");	// for(int i=1;i<=cnt;i++) printf("%d ",dp[1][i]);	// puts("");	for(int i=2;i<=n;i++)//转移	{		for(int j=1;j<=cnt;j++)//枚举i的状态		{			if(str[j] & map[i]) continue;//判断状态是否合法			for(int k=1;k<=cnt;k++)//枚举i-1的状态			{				if(str[k] & map[i-1]) continue;				if(str[j] & str[k]) continue;				dp[i][j]+=dp[i-1][k];			}		}	}	int ans=0;	for(int i=1;i<=cnt;i++)	{		if(map[n]&str[i]) continue;		ans+=dp[n][i];		ans%=mod;//重要，不加luogu会WA 10%	}	printf("%d\n",ans);	return 0;}
         
        
       
      
     

 　　　　小结：第2道状压。调试时候不要忘记题目所求的，在发现一个题与另一个题相似时不要被另一道题所局限