思路
这是一个状态压缩的一个经典问题,难点实在状态的定义和转移方程上。
状态定义:将每一列的看作是一个n长度的一个二进制数,0表示该位置有一个1×2的横向小方格的右半部分,这样就可以把一列的状态用一个数字表示出来,f[i][j]表示第i行的数字为j。
状态转移:
1.如果对于一列的其中一格来说已经有一个1×2的横向小方格的右半部在,那么就要求上一列,也就是左边一列的同行位置不能有一个1×2的横向小方格的右半部在。也就意味着一列的各个位置上的数和上一列的数不能同时为1,即 j&(j-1)=0;
2.如果一列里面有连续的0,那么就要用竖着的1×2的小方格填,那么这就要求一列不能用连续的奇数0,这就要求(j|k)里不能有连续的奇数0。
在做dp之前,我们还有做一个预处理,那就是把一列的所有情况是否有奇数0的结果存入一个布尔数组st里,以便dp判断用。
步骤
1.预处理
(中间有一步初始化,f[0][0]=1,0行j的值只能为0,因为不可能放小方块,并且这种情况只有一种)
2.枚举所有的列(循环一)
3.枚举所有列可能的情况(循环二)
4.枚举所有上一列可能的情况(循环三)
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=12;
long long f[N][1<<N];
bool st[1<<N];
int main(){
int n,m;
while(cin >> n >> m ,n||m){
for(int i=0;i<1<<n;i++){
st[i]=true;
int cnt=0;
for(int j=0;j<n;j++){
if(i>>j&1){
if(cnt&1){
st[i]=false;
cnt=0;
break;
}
}
else cnt++;
}
if(cnt&1)st[i]=false;
}
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<1<<n;j++){
for(int k=0;k<1<<n;k++){
if((j&k)==0&&st[j|k])f[i][j]+=f[i-1][k];
}
}
}
cout << f[m][0] << "\n";
}
}