poj2411 Mondriaan's Dream （轮廓线dp、状压dp）-程序员宅基地

Mondriaan's Dream

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 17203		Accepted: 9918

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

题意：

用 1 x 2 的矩形骨牌覆盖 h x w 的矩形，问有多少种不同的覆盖方法。

思路：

轮廓线dp（状压dp），以一个 w（矩形的宽） 位的二进制数（设为 k）表示一个状态，对应位上的 0 表示未覆盖的状态、1 表示已覆盖。

我们以从左到右、从上倒下的顺序做决策，要决策的点是 k 所表示的状态的下一个位置，以此点作为骨牌的右下角，

即：若我们在当前点竖着放置一块骨牌，它将覆盖当前点和正上方一点；若我们横着放置一块骨牌，它将覆盖当前点和左边的点。只有这样决策，才保证了是从之前的状态转移过来。

且以上述方式记录状态，k 的最高位正好是决策点的正上方一点，最低位是决策点的左边一点，并且我们每次决策都要保证最高位为 1 ，否则在以后的决策中都无法为其覆盖骨牌，也就无法达到全覆盖的要求。

这样，对于每个点都有三种决策方式：

1. 放一块竖着的骨牌，要满足的条件有：k 的最高位不为 1 ；当前点不在第一行。则转移后的状态是 curk = k<<1|1，左移一位并将最低位覆盖；
2. 放一块横着的骨牌，要满足的条件有：k 的最高位是1、最低位不试 1；当前点不在第一列。转移后的状态是 curk=(k|1)<<1|1，在覆盖最低位，左移一位后再覆盖最低位；
3. 不妨骨牌，要满足的条件有： k 的最高位是 1；状态 curk = k<<1；

注：每次状态转移后都要清除高于 w 位的多余位，这些并不是状态的一部分；左移得到下一状态应该好理解。

代码：

#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
const long long maxn = 12, INF = 0x3f3f3f3f;

long long dp[2][1<<maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long h, w;
    while(cin>>h>>w && (h+w))
    {
        memset(dp, 0, sizeof(dp));
        long long cur=0, curk;
        dp[cur][(1<<w)-1]=1;
        for(int i=0; i<h; ++i)
        {
            for(int j=0; j<w; ++j)
            {
                cur=1-cur;
                memset(dp[cur], 0, sizeof(dp[cur]));
                for(int k=0; k<(1<<w); ++k)
                {
                    if(i>0 && !(k&(1<<(w-1))))//放一块竖着的骨牌，覆盖当前位置和正上方的位置
                    {
                        curk=k<<1|1;
                        curk=curk&((1<<w)-1);//清除多余的位
                        dp[cur][curk]+=dp[1-cur][k];
                    }
                    if(j>0 && !(k&1) && (k&(1<<(w-1))))//放一块横着的骨牌，覆盖当前位置和左边的位置
                    {
                        curk=(k|1)<<1|1;
                        curk=curk&((1<<w)-1);
                        dp[cur][curk]+=dp[1-cur][k];
                    }
                    if((k&(1<<(w-1))))//不放
                    {
                        curk=k<<1;
                        curk=curk&((1<<w)-1);
                        dp[cur][curk]+=dp[1-cur][k];
                    }
                }
            }
        }
        cout<<dp[cur][(1<<w)-1]<<endl;
    }
    return 0;
}