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都比較小，可以用輪廓線，就是維護最后邊所需要的幾個狀態(tài)，然后進行DP。這里需要維護的狀態(tài)數(shù)就是min(n,m)。即大概是一行的大小。每次放的時候，只考慮（1）以當前格子為右方，進行橫放；（2）以當前格子為下方進行豎放；（3）還有就是可以不放。

3種都是不一樣的，所以前面的一種狀態(tài)可能可以轉(zhuǎn)為后面的幾種狀態(tài)，只要滿足了條件。條件是，橫放時，當前格子不能是最左邊的；豎放時，當前格子不能是最上邊的。而且要放的時候，除了當前格子，另一個格子也是需要為空才行的。

代碼關(guān)鍵部分給了注釋,請看：

#include #include #include #include using namespace std; long long dp[2][1<<11];//用滾動數(shù)組存儲輪廓線dp狀態(tài)數(shù)目 int n,m; int main(){ while(~scanf("%d %d",&n,&m) && (n || m)){ if((n&1) && (m&1))//如果n和m同時為奇數(shù)，則直接輸出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

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應(yīng)法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應(yīng)法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。