动态规划（状态压缩）

动态规划（状态压缩）

题目和代码源自

/*状态压缩的核心：讲每一行的状态用二进制来表示，然后转换成一个十进制数字，如果有M列，那么状态就有2^M个状态，那么就可以用0--2^M-1的数字来表示这些状态，一般情况下，M不得超过32位 一、先在dp里面准备好第一行的状态针对这道题来说，如果用竖着的瓷砖来铺的话，我们把下面的位置记做一，上面的位置记做零，如果是横着铺的，那么后一个位置一定为1， 二、从第二行开始，以后每一行是否可行要依据前一行的状态 
*/
/*状态压缩DP******填充地板  */  
#include <iostream>  
#include <algorithm>  
#include <memory.h>  
using namespace std;  
#define NMax 1000  
#define MMax 1<<5  bool testFirstLine(int j, int M) // 主要用来测试第一行的兼容性  
{
/*注意：左移是从从数字的二进制最右边开始移动的，所以，我们检测状态j的时候，是从最后一列开始检测的 
*/int i = 0;  while(i < M)   //第0、1、2、3列  {  if((j & (1<<i)) == 0)       // 判断j的第i位是否为0  为1则执行   如果第i为1 则其前一位为0  如果判断的第j位为1  其后一位必然为0  i++;  else if(i == M-1 || !(j & (1 << (i+1)))) //最后一列不为一；第i列为一，那么第i-1列必须为一 return false;  else i += 2;  //如果第i列为1且，第i-1列也为一，符合要求，则直接跳转到第i-2列 }return true;  
}bool testCompatible(int statesA, int statesB, int M)   // 判断下一行状态stateA与上一行状态stateB的兼容性  
{  int i = 0;  while(i < M)  {  if((statesA & (1<<i)) == 0){  //状态A为零，则状态B要满足要求，必须为一 if((statesB & (1<<i)) == 0)  {  return false;  }  i++;  }  else//状态A为1 {if((statesB & (1<<i)) == 0) i++;  //状态A为11状态B为一， 只要两个状态的中有一个 的 i-1位为零，就不符合要求 else if(i == M-1 || !((statesA &(1<<(i+1))) && (statesB &(1<<(i+1)))))  {  return false;  }  else i += 2;  }  }  return true;  
}  int main()  
{  int N, M;  cin >> N >> M;  if(M > N){  swap(M, N);  }  int allStates = 1 << M;  long long F[NMax][MMax];  int i,j;  memset(F, 0, sizeof(F));  for(j = 0; j < allStates; j++)  {  if(testFirstLine(j, M))  {  F[0][j] = 1; //第零行可行的状态 }  }  int k;//第i行每种状态与多少种i-1的每种状态兼容 for(i = 1; i < N; i++){  for(j = 0; j < allStates; j++){  for(k = 0; k < allStates; k++)  {  if(testCompatible(j,k,M))  {  F[i][j] += F[i-1][k]; //累加， F[i][j] = F[i][j] % 1000000007;  }  }  }  }  //为什么最后一行的最后一个状态就是答案呢？//因为最后一行必定全部都为一，如果存在某一列不为1，则这种状态不符合条件 cout << F[N-1][allStates-1]<< endl;  return 0;  
}