铺地砖|状压DP练习

有一个N*M(N<=5,M<=1000)的棋盘，现在有1*2及2*1的小木块无数个，要盖满整个棋盘，有多少种方式？答案只需要mod1,000,000,007即可。

//我也不知道这道题的来源QAQ

N和M的范围本应是相同的，但是题目给出的N的值很小，这就给我们提供了使用状压DP的思路。

假设第一列已经铺满，则第二列的情况只与第一列对它的影响有关，同理，第三列的情况也只与第二列对它的影响有关，我们可以利用二进制来表示某一列的情况，状态state表示某一列的状态，例如state=4，则此列状态为00100，用dp[i][state]表示第i列，第i-1列对它的影响为state的方案数，求每一列的方案数可以通过搜索来实现，dp[i][state]=sigma(dp[i-1][la]) la可以通过填放变为state。

代码：

 1 //铺棋盘
 2 //2015/10/22 
 3 #include<cstdio>
 4 #include<iostream>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<cstring>
 9 #include<algorithm>
10 #define maxn 100000000+50
11 #define inf 0x7fffffff
12 #define  xiao 1e-9
13 #define mod 1000000007
14 using namespace std;
15 int dp[1005][40],n,m;
16 void dfs(int i,int j,int state,int next)
17 {
18     if(j==n) 
19     {
20         dp[i+1][next]+=dp[i][state];
21         dp[i+1][next]%=mod; 
22         return;
23     }//如果枚举到了最后一行，则下一列状态为next时方案数加上此列状态为state的方案数
24     if(((1<<j)&state)>0) dfs(i,j+1,state,next);//如果第j行位置已被占用，直接跳过，搜索j+1行
25     if(((1<<j)&state)==0) dfs(i,j+1,state,next|(1<<j));//如果未被占用，尝试填放一个1*2的
26     if(j+1<n&&((1<<j)&state)==0&&((1<<(j+1)&state)==0)) dfs(i,j+2,state,next);//如果此位置以及下一位置都未被占用，尝试放一个2*1的
27     return;
28 }
29 int main()
30 {
31     cin>>n>>m;
32     memset(dp,0,sizeof(dp));
33     dp[1][0]=1;
34     for(int i=1;i<=m;++i)
35       for(int j=0;j<(1<<n);++j)
36         {
37             if(dp[i][j])  dfs(i,0,j,0);
38                     }
39     cout<<dp[m+1][0]<<endl;
40     return 0;
41  }