本文共 818 字，大约阅读时间需要 2 分钟。

题目大意：

有1*2和2*1两种骨牌， 问铺满m*n大小的矩形内可以有多少种铺法？

思路：

用二进制表示，连续两个00表示这两个格子是横放的， 用1表示这个格子是竖放的（是骨牌的上部分或者下部分）。

先处理得到所有符合条件的状态，即如果有0一定是要连续出现两个0.

对于第i行的状态j，j是1的地方，那么i-1行相同地方一定也要是1，0的地方是1或0都可以。 i行和i-1行都是1的地方，他们组成了一个竖放的骨牌，那么i-2行的这些地方，既可以是0也可以是1，所以递归时要把1变成0，这样的话i-2行的这个地方就可以是1或0.

用f[i][j] 表示第i行的j状态有多少种状态。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAX_STATE = (1<<11)+10;const int MAXN = 12;int n, m;int sta[MAX_STATE], idx;int64 f[MAXN][MAX_STATE];int maxState;bool ok[MAX_STATE];bool check(int sta){ int i=0; while(i < m){ if((sta>>i)&1) ++i; else{ if(i==m-1 || ((sta>>(i+1))&1)!=0) return false; i += 2; } } return true;}void init(){ memset(ok, 0, sizeof(ok)); maxState = (1<
        
       
      
     
    
   

转载地址：http://ivzni.baihongyu.com/