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 #include #include #include 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<

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。