POJ 2411 大矩形用1X2小矩形填充 状态dp DFS

这题和编程之美上面的“地板覆盖”问题有点像，不同的是，编程之美上面只需要判定能否覆盖，这题需要求出总方案数目

结题报告转自http://duanple.blog.163.com/blog/static/709717672008930104124684/

题意：给你一个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;
_int64 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;
}