327 玉米田（状态压缩dp）

左手的ㄟ右手 2022-09-12 07:47 20阅读 0赞

**1. 问题描述：**

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。非常遗憾，部分土地是不育的，无法种植。而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。现在给定土地的大小，请你求出共有多少种种植方法。土地上什么都不种也算一种方法。

**输入格式**

第 1 行包含两个整数 M 和 N。第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

**输出格式**

输出总种植方法对 10 ^ 8 取模后的值。

**数据范围**

1 ≤ M，N ≤ 12

**输入样例：**

2 3  
1 1 1  
0 1 0

**输出样例：**

*  9

来源：[https://www.acwing.com/problem/content/description/329/][https_www.acwing.com_problem_content_description_329]

**2. 思路分析：**

这道题目属于**状态压缩dp**的经典题目，形状属于"十"字形的约束，acwing1064题属于"井"字型约束，这两道题目其实是很像的，所以解决的思路也是类似的，可以对照着来理解。需要解决的两个问题：① 状态定义；② 状态计算；状态压缩dp的状态定义一般根据求解的问题以及相应的限制来定义的，类似于1064题我们可以定义一个二维数组dp（这道题目没有种植的数量的限制所以二维就可够了），其中dp\[i\]\[j\]表示已经摆好了前i行，并且第i行的状态为j的方案数目；怎么样进行状态的计算呢？状态计算对应集合的划分，一般是找最后一个不同点，可以发现当前的状态j是确定的，所以需要找上一个状态k，我们可以将集合划分为所有能够转移到当前状态的上一个状态，枚举所有上一个能够转移到当前状态的合法状态，然后累加到当前状态对应的方案数目即可。在状态计算之前我们需要先预处理所有合法的状态，这样可以避免计算不合法的状态导致时间复杂度很高的问题。一般预处理有两个过程：

*  先记录下每一行中不存在两个连续的1的合法状态
 *  记录当前的状态j可以由哪些合法状态k转移过来

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

class Solution:
        # 计算当前的sta是否有两个连续的1
        def check(self, sta: int, k: int):
            for i in range(k):
                if sta >> i & 1 and (sta >> i + 1 & 1): return False
            return True
    
        def process(self):
            n, m = map(int, input().split())
            # g数组来记录每一行不能够种的状态
            g = [0] * (n + 2)
            for i in range(1, n + 1):
                a = list(map(int, input().split()))
                t = 0
                for k in range(m - 1, -1, -1):
                    # 当a[k]为0的时候说明不能够种植, ^ 是异或操作0变成1, 1变成0
                    t += (a[m - k - 1] ^ 1) << k
                g[i] = t
            st = list()
            for i in range(1 << m):
                # 判断当前的状态i是否具有两个连续的1
                if self.check(i, m): st.append(i)
            state = [list() for i in range(1 << m)]
            for i in range(len(st)):
                for j in range(len(st)):
                    a, b = st[i], st[j]
                    # 当前状态a可以从上一个合法状态b转移过来
                    if a & b == 0:
                        state[a].append(b)
            # 这里有一个技巧是多声明一个长度这样状态计算的时候可以计算到n + 1行这样可以省略枚举答案的步骤
            mod = 10 ** 8
            dp = [[0] * (1 << m) for i in range(n + 2)]
            dp[0][0] = 1
            for i in range(1, n + 2):
                # 枚举当前这一行的状态
                for a in st:
                    for b in state[a]:
                        # 当前状态种植的玉米地方存在不能够种植的地方
                        if a & g[i]: continue
                        # 累加上上一个能够转移到当前状态的合法状态
                        dp[i][a] = (dp[i][a] + dp[i - 1][b]) % mod
            # 前n + 1行已经放好了, 并且第i + 1行状态为0的方案数目
            return dp[n + 1][0]
    
    
    if __name__ == '__main__':
        print(Solution().process())

[https_www.acwing.com_problem_content_description_329]: https://www.acwing.com/problem/content/description/329/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/bf019ebdc1964d09966ea34bd7dfb109.png