$$\color{Red}{从蒙德里安 ——> 小国王 ——> 玉米田 ——> 炮兵阵地 逐层分析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

司令部的将军们打算在 N×M
的网格地图上部署他们的炮兵部队。

一个 N×M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中X区域所示：

oooXooo
oooXooo
oXX*XXo
oooXooo
oooXooo

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式

第一行包含两个由空格分割开的正整数，分别表示 N
和 M；

接下来的 N 行，每一行含有连续的 M 个字符(P 或者 H)，中间没有空格。按顺序表示地图中每一行的数据。

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

数据范围

N≤100,M≤10

输入样例：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例：

6

思考

这道题可以看作玉米田的升级版，也是棋盘状压dp，但是十字扩大了一格，影响范围变成上下两行

而玉米田和小国王的思想极其类似蒙德里安的梦想，关于他们我有不下于千字的讲解，大家可以去看看，包括很多细节和边界条件的阐述

传送门：我的蒙德里安的题解

传送门：我的小国王题解

传送门：我的玉米田题解

我们发现这题也是棋盘类的状态压缩状态，第 i行的状态和前两行后两行都有关联，所以不妨我们就从上到下去枚举状态，这样考虑第i行的状态只需要考虑第i - 1行的状态，和第i - 2行的状态

那么我们的动态规划就可以这么来看f[i][j][k]---> 摆好第i行，前一行行状态为k，第i行状态为j的最大方案数量

再来说明一下一个状态如何才算合法

    static boolean check(int state) {
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1 && ((state >> i + 1 & 1) == 1 || (state >> i + 2 & 1) == 1))
                return false;
        }
        return true;
    }

如何计算当前状态的部队数量

    static int count(int state) {
        int count = 0;
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1)
                count++;
        }
        return count;
    }

需要满足一行有1的地方相邻两格没有1才行，为什么这道题没有考虑领边取或运算的计算？
小国王和我们蒙德里安部分的分析相同，它的影响范围是口字形，一个地方为1，会影响邻边的对角线位置元素也不能为1，当满足 (a & b) == 0 即两行没有交集算第一个合法条件，同时此时求a | b,代表两个状态求并集，这个理由在蒙德里安讲过，此时也需要满足并集状态也没有相邻的1

这道题影响范围是2格长度的十字形，只对领边相同位置有影响 因此只需要满足 (a & b) != 1 && (a & c) != 1 && (b & c) != 1 即可

我们的状态转移根据闫式dp分析法，可以这么考虑，当前的状态只能是合法的前一行(i - 1)的状态为k，合法的当前行(i)的状态为j的最大方案数量f[i&1][j][k]与不断枚举当前行的前两行，即i - 1行的状态l的情况下的前两行的状态组合 f[i-1&1][k][l] + cnt[j]
为什么最后多了两维遍历，答案是f[n+2&1][0][0]?
答案本来按我们原定想法是从最后一行f[i][][]循环找到底答案是状态为什么，可以利用遍历state，但是我们为什么多开两维的状态方程——》因为我们可以利用多计算一行的状态方程,此时n + 2行，并且i行和i - 1状态都为0，即没有任何部队，就是前n行合法的全部方案数

一个疑惑，为什么判断状态是否合法的时候，只判断了当前行和上一行，没有判断上上行是否合法？

这了从转移方程我们其实明白，我们更新状态其实用的是上一行的状态，转移到这一行，上一行的状态天然肯定需要满足上上行状态合法。

这里我们这么一直倒推到第一行，我们发现第一行的状态肯定不存在上上行，上一行合法的判断，多此一举，当我们已经把第一行的状态给确定并赋值，其实可以理解为，合法的能转移到下一行的状态已经被存储了，所以其实我们只判断当前行就行了，前两行合法的状态才会有合法的状态方程转移过来，不合法的，必然方程值为0

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int N = 110, M = 1 << 10;
    static int[][][] f = new int[2][M][M];
    static int n, m;
    static List<Integer> state = new ArrayList<>();
    static ArrayList<Integer>[] head = new ArrayList[M];
    static int[] g = new int[N];
    static int[] cnt = new int[M];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static boolean check(int state) {
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1 && ((state >> i + 1 & 1) == 1 || (state >> i + 2 & 1) == 1))
                return false;
        }
        return true;
    }

    static int count(int state) {
        int count = 0;
        for (int i = 0; i < m; i++) {
            if ((state >> i & 1) == 1)
                count++;
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        //每行的非法状态数组
        for (int i = 1; i <= n; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < chars.length; j++) {
                //把非法的位置为1 合法置为0
                if (chars[j] == 'H')
                    g[i] += 1 << j;
            }
        }
        //合法单行状态储存
        for (int i = 0; i < 1 << m; i++) {
            if (check(i)) {
                state.add(i);
                cnt[i] = count(i);
            }
        }
        //动态规划
        for (int i = 1; i <= n + 2; i++) {
            //当前行
            for (int j = 0; j < state.size(); j++) {
                //前一行
                for (int k = 0; k < state.size(); k++) {
                    //倒数第一行
                    for (int l = 0; l < state.size(); l++) {
                        int a = state.get(j);
                        int b = state.get(k);
                        int c = state.get(l);
                        if ((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
                        if ((g[i] & a) != 0 || (g[i-1] & b) != 0) continue;
                        f[i & 1][j][k] = Math.max(f[i & 1][j][k], f[i - 1 & 1][k][l] + cnt[a]);
                    }
                }
            }
        }
        System.out.println(f[n+2 & 1][0][0]);
    }
}