网站后台密码错误/2021网络营销成功案例

问题 A: 铺砖块

时间限制: 1 Sec  内存限制: 128 MB
提交: 117  解决: 70
[提交][状态][讨论版]

题目描述

现有n*m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种 

 

输入

输入n，m（1<=n, m<=11) 
有多组输入数据，以m=n=0结束 

 

输出

输出铺砖块的方案数

 

样例输入

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

样例输出

1
0
1
2
3
5
144
51205

状态压缩类的题目，主要将dp[i][j]表示填满第i层后，对下一层影响为j，如果用数组代替，转移起来空间将会非常大，而且也是十分麻烦的，但是这里发现，它的
宽度非常小，长度可以段，可以用二进制位压入，来进行转移。通过计算，发现从上一层转移到下一层的状态并不是（2^10*2^10） 大概是20000左右吧，大神推出来的，但是我还是开了1000000
这还让xqj大神帮我查了一下，刚开始还爆了空间，真的无语。

#include<cstdio> 
#include<algorithm> 
#include<cmath> 
#include<iostream> 
#include<climits> 
#include<map> 
#include<string> 
#include<cstring> using namespace std; 
const int MAXN=1<<12; struct fzy 
{ int start,end;   
}flag[(MAXN>>1)*(MAXN>>1)]; 
int n,m,num; 
long long dp[12][MAXN]; void dfs(int sta,int start,int end) 
{ if (sta>m) return; if (sta==m) { flag[++num].start=start; flag[num].end=end; return; } dfs(sta+1,(start<<1)+1,end<<1); dfs(sta+1,start<<1,(end<<1)+1); dfs(sta+2,start<<2,end<<2); 
} 
void solve() 
{ if (n*m%2==1)  { cout<<0<<endl; return; } num=0; memset(dp,0,sizeof(dp)); dfs(0,0,0); dp[0][0]=1; for (int i=1;i<=n;i++) { for (int j=1;j<=num;j++) dp[i][flag[j].end]=dp[i][flag[j].end]+dp[i-1][flag[j].start]; } cout<<dp[n][0]<<endl; 
} 
int main() 
{ while (scanf("%d%d",&n,&m)&&(n+m)) { solve(); } 
}