292 炮兵阵地（状态压缩dp）

梦里梦外; 2022-09-12 08:59 207阅读 0赞

**1. 问题描述：**

司令部的将军们打算在 N×M 的网格地图上部署他们的炮兵部队。一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16][]  
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

**输入格式**

第一行包含两个由空格分割开的正整数，分别表示 N 和 M；接下来的 N 行，每一行含有连续的 M 个字符(P 或者 H)，中间没有空格。按顺序表示地图中每一行的数据。

**输出格式**

仅一行，包含一个整数 K，表示最多能摆放的炮兵部队的数量。

**数据范围**

N ≤ 100，M ≤ 10

**输入样例：**

5 4  
PHPP  
PPHH  
PPPP  
PHPP  
PHHP

**输出样例：**

6  
来源：[https://www.acwing.com/problem/content/description/294/][https_www.acwing.com_problem_content_description_294]

**2. 思路分析：**

这道题目属于**状态压缩dp**的经典题目，可以看成是[acwing327题玉米田][acwing327]的简单扩展，327题在种植玉米的时候是"十"字型的限制，这道题目是在"十"字型四周的基础上各扩展了一个位置，限制更强了，所以当前这一行的状态不仅与上一行有关系，而且与上两行也是有关系的，327题由于当前这一行的状态只与上一行有关系，所以在状态表示的时候声明一个二维数组即可，这道题目与上两行是有关系的所以我们想到可以多声明一维来记录倒数第二行的状态，这样就可以清晰地描述状态之间的转移关系。动态规划一般包括两个步骤：① 状态表示；② 状态计算；我们可以声明一个三维数组dp，其中dp\[i\]\[a\]\[b\]表示前i行已经摆好了，第i行的状态是a，第i - 1行的状态是b能够放置最大炮兵部队的数目；怎么样进行状态计算呢？状态计算对应集合的划分，一般是找最后一个不同点，我们在状态计算的时候枚举当前第i行的状态，i - 1行的状态，i - 2行的状态，分别对应a，b，c，枚举的时候相当于是固定了当前第i行，i - 1行的状态为a，b，我们需要尝试当前状态是否可以由倒数第一行与第二行的状态转移过来呢，怎么样判断当前的三个状态是合法的呢？其实需要满足两个条件：

*  a，b，c三行对应的列是没有冲突的，也即a & b == 0 and a & c == 0 and b & c == 0（当相与结果不为0说明至少存在某一列是有冲突的，两列中的某个位置都为1所以就冲突了）
 *  因为我们是一行一行放置的，所以对于当前这一行有的位置可能是山地，而这些位置是不能够放置炮兵部队的，所以在放置第i行的时候先判断一下当前尝试的状态1的位置是否是山地即可，如果是山地那么跳过当前的状态即可

在状态计算之前需要先预处理合法的状态，对于每一行状态对应的二进制数字，若当前位置是1那么右边两个相邻的位置不能够存在1，如果存在1说明会发生冲突，所以需要先记录下每一行放置的炮兵部队合法的状态，对于这道题目只需要一个预处理即可，我们可以在状态计算的时候跳过其余不合法的状态即可。在状态计算的时候使用四层循环枚举，第一层循环枚举当前是第i行，第二层循环枚举第i行的状态a，第三层循环枚举i - 1行的状态b，第四层循环枚举i - 2行的状态c；尝试当前这一行状态为a上一行状态是b的时候是否可以由上一个状态转移过来，其实可以看成固定第i行和i - 1行的状态，然后计算由上一个状态转移到当前状态的能够放置的最大炮兵数量即可，我们可以先判断a，b，c三个状态对应的每一列是否存在冲突，并且判断当前第i行尝试的状态是否与当前这一行山地的位置存在冲突，如果存在冲突直接continue这些状态即可。（我们在一开始的时候就保证了第一行中所有的状态是合法的，所以在后面状态计算的时候只有这些合法的状态才是有值的）

**3. 代码如下：**

**python滚动数组优化：其实很简单，因为我们只需要使用到i - 1和i的状态，所以我们可以使用滚动数组来优化，先写不滚动的然后与1相与即可，因为i和i - 1其中一个一定是奇数另外一个是偶数，所以对于第一维就可以实现滚动的效果：**

class Solution:
        # 判断当前是否存在位置是否存在两个连续的1或者三个连续的1
        def check(self, sta: int, k: int):
            for i in range(k):
                if (sta >> i & 1) and (sta >> i + 1 & 1 or sta >> i + 2 & 1): return False
            return True
        
        # 计算当前sta状态对应的二进制的1的数目
        def count(self, sta: int, k: int):
            res = 0
            for i in range(k):
                if sta >> i & 1: res += 1
            return res
    
        # 滚动数组优化
        def process(self):
            n, m = map(int, input().split())
            # g用来记录矩阵中高原与平地的情况, 这样后面在状态计算的时候判断当前状态放的炮是否有在山地上, 两个状态相与即可判断是否在山地的位置放置可炮兵部队
            g = [0] * (n + 1)
            for i in range(1, n + 1):
                s = input()
                t = 0
                for j in range(len(s)):
                    c = s[j]
                    if c == "H":
                        t += 1 << len(s) - j - 1
                g[i] = t
            # state记录每一行放置的炮兵部队没有冲突的状态, 这里只需要一个预处理然后在状态计算的时候然后再筛选掉一些不合法的状态
            state = list()
            for i in range(1 << m):
                if self.check(i, m):
                    state.append(i)
            dp = [[[0] * (1 << m) for i in range(1 << m)] for i in range(2)]
            for i in range(1, n + 1):
                for j in range(len(state)):
                    for k in range(len(state)):
                        for u in range(len(state)):
                            # a为第i行的状态, b为第i - 1行的状态, c为i - 2行的状态, 顺序无所谓只需要一一对应起来(状态计算的时候对应起来即可)
                            a, b, c = state[j], state[k], state[u]
                            # 判断当前三行是否存在交集, 也即每一列的位置是否存在1如果存在1说明竖着的位置存在冲突
                            if a & b or a & c or b & c: continue
                            # 第i行的状态放置的炮兵的是否与山地存在冲突
                            if a & g[i]: continue
                            # 枚举的当前第i行和i - 1行, i - 2行的状态不存在冲突, 上一个状态转移到当前状态需要累加上当前这一行的状态对应的炮兵数量取一个max即可
                            dp[i & 1][a][b] = max(dp[i & 1][a][b], dp[i - 1 & 1][b][c] + self.count(a, m))
            # 枚举答案, 枚举第n行与状态为i和第i - 1行状态为j的最大值即可
            res = 0
            for i in range(1 << m):
                for j in range(1 << m):
                    res = max(res, dp[n & 1][i][j])
            return res
    
    
    if __name__ == '__main__':
        print(Solution().process())

**没有经过滚动数组优化所以超出空间的限制：**

class Solution:
        # 判断当前是否存在位置是否存在两个连续的1或者三个连续的1
        def check(self, sta: int, k: int):
            for i in range(k):
                if (sta >> i & 1) and (sta >> i + 1 & 1 or sta >> i + 2 & 1): return False
            return True
        
        # 计算当前sta状态对应的二进制的1的数目
        def count(self, sta: int, k: int):
            res = 0
            for i in range(k):
                if sta >> i & 1: res += 1
            return res
    
        def process(self):
            n, m = map(int, input().split())
            # g用来记录矩阵中高原与平地的情况, 这样后面可以方便判断是否可以放置炮
            g = [0] * (n + 1)
            for i in range(1, n + 1):
                s = input()
                t = 0
                for j in range(len(s)):
                    c = s[j]
                    if c == "H":
                        t += 1 << len(s) - j - 1
                g[i] = t
            # state记录每一行放置的炮兵部队没有冲突的状态, 这里只需要一个预处理然后在状态计算的时候然后再筛选掉一些不合法的状态
            state = list()
            for i in range(1 << m):
                if self.check(i, m):
                    state.append(i)
            dp = [[[0] * (1 << m) for i in range(1 << m)] for i in range(n + 1)]
            for i in range(1, n + 1):
                for j in range(len(state)):
                    for k in range(len(state)):
                        for u in range(len(state)):
                            # a为第i行的状态, b为第i - 1行的状态, c为i - 2行的状态, 顺序无所谓只需要一一对应起来(状态计算的时候对应起来即可)
                            a, b, c = state[j], state[k], state[u]
                            # 判断当前三行是否存在交集, 也即每一列的位置是否存在1如果存在1说明竖着的位置存在冲突
                            if a & b or a & c or b & c: continue
                            # 第i行的状态是否与某些位置是山地存在冲突
                            if a & g[i]: continue
                            # 枚举的当前第i行和i - 1行, i - 2行的状态不存在冲突, 
                            dp[i][a][b] = max(dp[i][a][b], dp[i - 1][b][c] + self.count(a, m))
            # 枚举答案, 枚举第n行与状态为i和第i - 1行状态为j的最大值即可
            res = 0
            for i in range(1 << m):
                for j in range(1 << m):
                    res = max(res, dp[n][i][j])
            return res
    
    
    if __name__ == '__main__':
        print(Solution().process())

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6e44b0cc7eff481e8f184dfd31a43f96.png
[https_www.acwing.com_problem_content_description_294]: https://www.acwing.com/problem/content/description/294/
[acwing327]: https://blog.csdn.net/qq_39445165/article/details/120422971