题目的意思是这样的：http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
给你一个h*w的矩形，用一个1*2的小矩形去填充，问有多少种填充方法，不考虑对称性。
关键点提示：
1.DFS部分
实际上是在枚举第i行的放置方法，由此便可以确定出该行及上一行的状态。
对于第i行，状态(参数next_stat)的定义是指，前i-1行完全放满，第i行的所有位置是否放置(0,1表示)组成的二进制序列，转化为十进制数后所代表的状态。
放置方法，总共存在三种，
1. 竖直放置
2. 水平放置
3. 不放置
以竖直放置举例说明：
假设第i行的第3列位置是要竖直放置，则说明它的前一行该列位置必然是0，放置后这一行的状态必然变成了1，所以上一行的状态应该是prev_stat << 1，该行是(next_stat << 1)|1，直到column == w，即从左到右开始枚举，枚举到了最右列，说明该放置方案完毕。
本质上是枚举的第i行的放置方案，而放置方案实际上确定了上下两行的状态。
2.注意到prev_stat并没有明确指明列值，对于列的变化实际上是通过移位来反映的。
prev_stat,next_stat初始均为0，第一次移位确定的是左边第一个位置的状态，这样随着移位的进行这个状态不断的往高位迁移，这样在以后的移位，或运算中保证保持不变。也就是说，随着移位的进行，本来第一位表示的是最左边那列的状态，慢慢得变成第2，3，4，...w位来表示它的状态，实际上是该状态值不断得伴随着移位再向高位迁移。
DFS+DP解法解题报告：
当高度和宽度都为奇数时显然答案为0, 这个用面积的奇偶性就很容易得证
记f[i][s1]为第i-1行全满且第i行状态为s1时的种数，便有如下递推关系:
f[i][s1] = sigma(f[i-1][s2]);
其中(s1, s2)整体作为一个放置方案， 这样f[h+1][0]即是答案了
对于每一个位置，我们有三种放置方法：
1. 竖直放置
2. 水平放置
3. 不放置
d为当前列号 ，初始化d, s1, s2都为0;对应以上三种放置方法，s1, s2的调整为:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
先就第一种情况解释一下，另外的两种情况可以类推
S1<<1|1即为把s1的二进制表示后面加上一个1，对就于本题来说就是(d+1)列上放
置，s2<<1即为把s2的二进制表示后面加上一个0，对于本题来说就是(d+1)列上不放置。
但为什么s1、s2会如此变化呢？本人在此处想了好长时间，后来想明白了，s1对应于本行的状态，s2对应
于上一行的状态，能竖直放置意味着上一行的(d+1)列是空着的，因此此时上一行的状态为s2<<1，同时竖
置放置了之后，则本行(d+1)行放置了东西，状态于是变为s1<<1|1;
当d = w时保存状态
对于初始时的f值，可以假设第0行全满，第一行只有两种放法:
1. 水平放置 d = d + 2, s << 2 | 3;
2. 不放置 d = d + 1, s << 1;
另外，利用滚动数组，可以减少空间的开销
还有一个可以提高较率的地方，当输入的 w > h 时，对调，因为横向的运算是指数
级的， 而列向的是线性的.
附代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAX (1<<11)+1
int w;
long long a[2][MAX];
int t;
//DFS枚举第i行的放置情况(保证第i-1行放满)，由此确定该行及第i-1行的状态，为节约空间，使用滚动数组实现
void DFS(int column,int next_stat,int prev_stat){
if(column == w){a[t][next_stat] += a[(t+1)%2][prev_stat];return;}
if(column + 1 <= w){
DFS(column+1,next_stat << 1 , (prev_stat << 1)|1);//不放置
DFS(column+1,(next_stat << 1)|1,prev_stat << 1); //竖直放置
}
if(column + 2 <= w)
DFS(column+2,(next_stat << 2)| 3,(prev_stat << 2)|3);//水平放置
}
int main(){
int h;
while(scanf("%d%d",&h,&w) &&(h != 0 || w != 0)){
if(h == 0 || w == 0 || (h*w)%2 == 1){printf("0\n");continue;}
if(w > h){ w ^= h; h ^= w; w ^= h;}
memset(a,0,sizeof(a));
t = 0;
a[t][(1 << w) - 1] = 1;//初始化，相当于第0行全满，所以只有该状态数为1，其他状态方法均为0.
for(int i = 1 ; i <= h ; i++){
t = (t+1)%2;
DFS(0,0,0);
memset(a[(t+1)%2],0,sizeof(a[0]));
}
printf("%I64d\n",a[t][(1 << w) -1]);
}
return 0;
}
/*
//printf-table
# include <stdio.h>
__int64 a[11][11]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n&&m)
printf("%I64d\n",a[n-1][m-1]);
return 0;
}
*/
评论