POJ3254（状态压缩dp）：玉米地

POJ3254（状态压缩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
Corn Fields
Time Limit: 2000MS        Memory Limit: 65536K
Total Submissions: 26638        Accepted: 13894
Description

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)
Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.
Sample Input

2 3
1 1 1
0 1 0
Sample Output

9
Hint

Number the squares as follows:
1 2 3
  4  

There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
Source

USACO 2006 November Gold

我的代码

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
可以发现这个题有如下特征，规模较小，每个方格只有两种状态，可以种玉米和不可以种玉米；

仍然考虑用状压dp；

定义状态：

定义状态dp[i][state]表示能到达第i行，且第i行的所有的种玉米和不种玉米的情况为state时的所有状态数。

种玉米代表1，不种玉米代表0；

分析这个状态定义，发现这个状态定义把整个问题分成了n个阶段(代表行数)，并且这n个阶段遵循无后效性；

状态转移：

当前阶段只受前一阶段的影响，当前阶段只能影响到后一阶段。所以状态转移就是把握住当前状态是如何影响后一

阶段的。在这个题中，我们会发现：

如果当前阶段的某列土地种了玉米，那么下个阶段的这列土地就不能种玉米。

另外，如果当前阶段某列土地的前一列土地种了玉米，那么这一列就不能再种玉米了。

需要注意的是，如果当前阶段的某一列可以种玉米，你可以有两种选择，种或不种。

按一个方向求解：

可以看出这个状态定义是按行数分了n个阶段，所以我们应该按照行数来进行求解，根据状态定义，结果是把最后

一行的所有可达到的状态的方法数加和即可。

解答

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
97
98
99
100
101
102
103
#include<stdio.h>
#include<string.h>
#define mmset(a,b) memset(a,b,sizeof(a))
 
const int INF = 1 << 12 + 5;
int   dp[15][INF];
int data[15][15];
int n,m;        //行列 
 
/*
2 3
1 1 1
0 1 0
Sample Output
9
*/
 
 
/*
i代表当前行 
j代表当前列
state代表当前行(阶段)的状态 
next代表下一行(阶段)的可到达状态
flag代表是上一列是否种了玉米，如果种了玉米，flag =  1,否则等于0； 
*/ 
void dfs(int i,int j,int state,int next,int flag);
 
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                scanf("%d",&data[i][j]);
            }
        }
        mmset(dp,0);        //初始化 
        dp[0][0] = 1;    
        
        /*
            遍历每个阶段的所有可达到状态，并搜索这种状态所能到达所有状态 。
            这是状态转移的过程 
        */ 
        for(int i = 0; i < n; i++)    
        {
            for(int state = 0; state < (1<<m); state++)
            {
                if(dp[i][state] > 0)
                {
                    dfs(i,0,state,0,0);
                }
            }
        }
        int ans = 0;
        /*
            求解，对最后一行所有可达到的状态的方法数加和，并存在变量ans中; 
        */ 
        for(int state = 0; state < (1<<m); state++)
        {
            if(dp[n][state] > 0)
            {
                ans=(ans+dp[n][state])%100000000;
            }
        }
        printf("%d\n",ans);
    }    
    
    return 0;
}
 
void dfs(int i,int j,int state,int next,int flag)
{
    if(j == m) 
    {
        dp[i+1][next] = (dp[i+1][next] + dp[i][state])%100000000;
    }
    /*
    下面这段代码有点绕，可以种玉米是指客观条件,
    但种不种玉米是主观意愿。 
    */ 
    else
    {
        //表示可以种玉米 
        if(data[i+1][j] == 1 && (state & (1<<j)) == 0 && flag== 0) 
        {
            if(flag == 0||flag == 1)    //不种玉米 
            {
                 dfs(i,j+1,state,next,0);
            }
            if(flag == 0)    //种玉米 
            {
                dfs(i,j+1,state,next | (1<<j),1);
            }
        }
        //不可以种玉米 
        else
        {
            dfs(i,j+1,state,next,0);
        }
    }
}

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