POJ2411（状态压缩dp）：方格覆盖

POJ2411（状态压缩dp）：方格覆盖

========================

题目如下：

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
Mondriaan's Dream
Time Limit: 3000MS        Memory Limit: 65536K
Total Submissions: 27144        Accepted: 14765
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
Source

Ulm Local 2000

我的代码

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
这个题规模比较小，而且每个方格只有两种状态，分别是被覆盖和未被覆盖；

所以我们考虑用状态压缩dp；

定义状态：

我们首先定义状态：dp[j][state]，表示能到达第j列，且第j列所有方格的覆盖情况为state时的所有方法数；

这样我们通过这个状态把这个问题分为j个阶段(j代表列数),因为第j列放置的情况最多只能影响到j+1列。比如第j列放置

一个或多个1*2的方格。这样一种情况就会影响到j+1列；但是他最多影响到第j+1列，之后就不能再影响了。

这就是无后效性；无后效性是保证能动态规划的关键。

状态转移：

当第i列第j行状态为0时，表示没有覆盖；当为1时，说明被覆盖了；

如果当前格没有被覆盖，说明我们至少可以放一个1*2的方格，如果当前列的下一行也没有被覆盖，那么我们可以放一个

2*1的方格；如果被覆盖， 那么我们继续往当前列的下一行遍历 ，直到把这一列遍历完； 在这个过程中 ，我们能求出

下一列的合法状态(也就是可以到达的状态)，这是一个搜索的过程，至于为什么要搜索，请看下面：

我们把当前列每一种状态都进行搜索，看能不能找到从这种状态到其他状态的一种路径；如果存在，说明其他状态是

可以到达的。所以我们其实并不需要对每一种状态进行搜索，只需要对可以到达的状态进行搜索即可；

按一个方向求出该问题的解：

当前阶段总是影响下一阶段，所以我们应该按照阶段的方向进行求解，在这个题中是按列的方向求解；题目要求全部填

满，所以答案应该是dp[m+1][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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<stdio.h>
#include<string.h>
#define mmset(a,b) memset(a,b,sizeof(a))
const int INF = 1 << 12 + 10;
long long dp[13][2100];
int n,m;
/*
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
*/
 
 
/*搜索从第j列的state状态开始，它能到达第j+1列的哪些状态；
  i代表第i行，next代表它能到达第j+1列的next状态 
*/
void dfs(int i,int j,int state,int next);        
                                                
int main()
{
    
    while(~scanf("%d%d",&n,&m) && (n+m))
    {
        if(n > m)    //交换两个变量 
        {
            n = n ^ m;
            m = n ^ m;
            n = n ^ m; 
        }
        mmset(dp,0);    //初始化 
        dp[1][0] = 1;
        
        for(int j = 1; j <= m; j++)        //状态转移 
        {
            for(int state = 0; state < (1 << n); state++)
            {
                //对能达到的状态进行搜索，看该状态能不能达到其他状态；
                if(dp[j][state] > 0)     
                {
                    dfs(0,j,state,0);
                }
            }
        } 
        printf("%lld\n",dp[m+1][0]);        //输出答案 
        
        
    }
    return 0;
} 
 
void dfs(int i,int j,int state, int next)
{
    if(i == n)
    {
        /*
        注意dp[i][j]代表的含义，就知道为什么
        dp[j+1][next] += dp[j][state]
        */
        dp[j+1][next] += dp[j][state];        
        return;                                
    }
    else
    {
        if((state&(1 << i) )== 0)    //当该格子没被覆盖说明可以放一个1*2的木板 
        {
            dfs(i+1,j,state,next | (1<< i));
        }
        /*
        当该格子没被覆盖且它下面的格子也没被覆盖 
        说明可以当一个2*1的木板
        */ 
        if(i + 1 < n &&(state & (1 << i)) == 0 && (state & (1 << (i+1))) == 0)    
        {                                                                        
            dfs(i+2,j,state,next);
        }
        if((state & (1 << i)) > 0)    //当该格子被覆盖时，说明这个格子什么都不能放 
        {
            dfs(i+1,j,state,next);
        }
    }
}

题目链接：http://poj.org/problem?id=2411