A - Mondriaan's Dream

Time limit 3000ms     Memory limit 65536 kB

链接：
http://poj.org/problem?id=2411
https://vjudge.net/contest/145682#problem/A

状态压缩入门

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways. 

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

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

题意：

一个h*w的方格，让你用若干个长为2，宽为1的矩形把它填满，问最多有多少种方案
该题应用状压DP，总共有两种放法：向左放和向上放（向左向右或向上向下只是相对而言的）；当放第i排的时候有以下几种考虑：
设此时的位置为第r列
1、先看该列的第i-1行对应的位置是否填充好，如果该位置为空，则应该优先把它填满。
2、在该位置的第i-1行是填充的情况下，再判断该位置的左方是否填充，如果没有填充，则你可以选择填或不填（注意：我们这里是要求它总共有多少种方案把它填满）
用状压DP求解，dfs遍历时要注意以上的问题啊啊啊啊啊啊啊！！！！！！
用二进制来表示它是否被填充，当该位为1时表示填充，当该位为0时，表示未被填充！！！
注意按位与、按位或！！！！

完整代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define  ll long long
ll dp[15][2100];
ll h,w,i;
void dfs(ll r,ll now,ll ago)///分别表示此时位置，现在的状态，上一行的状态;
{
    if(r==w)///跑到最后一列时;
    {
        dp[i][now]+=dp[i-1][ago];///就把它加起来
        return;
    }
    /**下面分为必须填和可以不填两种情况
    /**竖着放**//**必须要放的情况*/
    if(!(ago&(1<<r)))///该排的上一排的对应位置为0;
        dfs(r+1,now|(1<<r),ago);///将现在的位置置1;
    /**另一种情况**/
    else
    {
        /**可以横着放**/
        if(r&&!(now&(1<<r-1)))///当它满足这个条件:r不在第0位且它的左一位也为0的时候,就有这一条路径;
            dfs(r+1,now|(1<<(r-1))|(1<<r),ago);///将它的前一位和本位都置1;
        /**可以横着放的时候你也可以不放**//**注意我们要计算的是可以放满的种数*/
        dfs(r+1,now,ago);///不跑该位！！！！！zz啊啊啊啊啊啊！我的天哪！！！！！ 
    }
}
int main()
{
    while(scanf("%lld%lld",&h,&w),h+w)
    {
        memset(dp,0,sizeof(dp));
        ll m=(1<<w)-1;///二进制......每一位都为1;
        dp[0][m]=1;///将第0行初始化为1;
        for(i=1;i<=h;i++)
            for(int j=0;j<=m;j++)
                if(dp[i-1][j])///只有在上一排有效才进行遍历
                     dfs(0,0,j);
        printf("%lld\n",dp[h][m]);
    }
    return 0;
}