POJ 2411 Mondriaan's Dream (轮廓线DP代码详解)

Mondriaan’s Dream（POJ 2411）

Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 18772 Accepted: 10717
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

（第一次认识轮廓线DP。。。只想感叹一句，DP深似海~）

题意：有一个n*m的棋盘，要求用1*2的骨牌来覆盖满它，有多少种方案？（n<12，m<12）
思路：

　　由于n和m都比较小，可以用轮廓线，就是维护最后边所需要的几个状态，然后进行DP。这里需要维护的状态数就是min(n,m)。即大概是一行的大小。每次放的时候，只考虑（1）以当前格子为右方，进行横放；（2）以当前格子为下方进行竖放；（3）还有就是可以不放。

　　3种都是不一样的，所以前面的一种状态可能可以转为后面的几种状态，只要满足了条件。条件是，横放时，当前格子不能是最左边的；竖放时，当前格子不能是最上边的。而且要放的时候，除了当前格子，另一个格子也是需要为空才行的。

代码关键部分给了注释,请看：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long long dp[2][1<<11];//用滚动数组存储轮廓线dp状态数目
int n,m;
int main(){
    while(~scanf("%d %d",&n,&m) && (n || m)){
        if((n&1) && (m&1))//如果n和m同时为奇数，则直接输出0，不可能铺满
        {
            printf("0\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        if(m>n)swap(m,n);//使得n>m,即窄列
        int h = 1 <<(m-1);//只有最高位为1
        dp[0][(1<<m)-1] = 1;
        int cur = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cur^=1;
                memset(dp[cur],0,sizeof(dp[cur]));
                for(int k = 0; k <(1<<m); k++)
                {
                    if(k & h)//[i,j]上面的格子为1，即[i-1,j]已经被填满
                    {
                        dp[cur][(k^h)<<1]+=dp[cur^1][k];//[i,j]不填充
                        if(j && !(k&1))//[i,j-1]未填充且j不是第一列
                        {
                            //可以横向填充，即将[i,j-1]与pi,j]填为1
                            dp[cur][((k^h)<<1)|3] += dp[cur^1][k];//k^h是为了把k的最高位变成0，移位的时候可以舍掉，其余的位不发生改变(位运算真是666)
                        }
                    }
                    else{
                        if(i)//上面的格子[i-1,j]未被填充，那[i,j]只能竖向填充，否则将永远无法填充到[i-1,j]
                            dp[cur][((k&(h-1))<<1)|1] += dp[cur^1][k];//k&(h-1)是为了把k的最高位变成0，移位的时候可以舍掉，其余的位不发生改变(位运算真是666)
                    }
                }
            }
        }
        printf("%lld\n",dp[cur][(1<<m)-1]);
    }
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/79365750