题意：给一个n*m的方格，用1*2和2*1的方格填满，有多少种方案。n、m<=11。
Sample Input
1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0
Sample Output
1 0 1 2 3 5 144 51205
题解：我们发现n、m很小，状压dp即可，状态转移如下
1 void dfs(int i,int j,int sta,int nex){ 2 //第i列、j+1行,当前状态sta,下列状态nex 3 if(j==n){f[i+1][nex]+=f[i][sta];return;} 4 if(((1<<j)&sta)>0) dfs(i,j+1,sta,nex); 5 //若此位置被上列占用,跳过 6 if(((1<<j)&sta)==0) dfs(i,j+1,sta,nex|(1<<j)); 7 //若此位置为空,尝试放1*2 8 if(j+1<n&&((1<<j)&sta)==0&&((1<<(j+1))&sta)==0) dfs(i,j+2,sta,nex); 9 //若次位置及下个位置都空,尝试放2*1 10 return; 11 }
初始状态为f[1][0]=1,最终答案为f[m+1][0]。
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 int n,m; 6 long long f[20][2050]; 7 void dfs(int i,int j,int sta,int nex){ 8 if(j==n){f[i+1][nex]+=f[i][sta];return;} 9 if(((1<<j)&sta)>0) dfs(i,j+1,sta,nex); 10 if(((1<<j)&sta)==0) dfs(i,j+1,sta,nex|(1<<j)); 11 if(j+1<n&&((1<<j)&sta)==0&&((1<<(j+1))&sta)==0) dfs(i,j+2,sta,nex); 12 return; 13 } 14 int main() 15 { 16 while(~scanf("%d%d",&n,&m)){ 17 if(!n&&!m) break; 18 memset(f,0,sizeof(f)); 19 f[1][0]=1; 20 for(int i=1;i<=m;i++) 21 for(int j=0;j<(1<<n);j++) 22 if(f[i][j]) dfs(i,0,j,0); 23 printf("%lld ",f[m+1][0]); 24 } 25 return 0; 26 }