形式化题目

给定 $N \times M$ 的网格，每格标为平原 P 或山地 H。在平原格上放置若干门炮，每格至多一门；两门炮会互相攻击，当且仅当它们同行且列距 $\leqslant 2$，或者同列且行距 $\leqslant 2$（攻击是横竖各两格的十字形，不受地形阻挡，斜方向不算）。求在任意两门炮都不互相攻击的前提下，最多能放置多少门炮。

正解

思路

题面给出 $N \le 100$、$M \le 10$：行数很大而列数很小。逐格枚举是 $2^{NM}$（$NM$ 可达 1000），指数爆炸；而 $2^M \le 1024$ 却完全可控。这已经指明了方向——按行推进，把列方向压成掩码。下面逐步把这个方向落实。

第一步：把"攻击"写成坐标条件。

设两门炮位于 $(r_1, c_1)$ 与 $(r_2, c_2)$。攻击范围是横向左右各 2 格、纵向上下各 2 格的十字形，所以它们互相攻击当且仅当

斜方向（比如 $(1,1)$ 与 $(2,2)$）不构成攻击。这一点必须确认，否则会把答案算小：例如

1
2
3
43 2
HP
PP
HP

正确答案是 2（$(1,2)$ 与 $(2,1)$ 是斜向相邻，互不攻击），若误加斜向约束就只剩 1 门；而 $(1,2)$ 与 $(3,2)$ 虽然隔了一行，但同列 $c_2$ 且行距恰为 2，仍然互相攻击。

第二步：观察"行内合法方案"只由 $M$ 决定。

同一行里两门炮的列距要 $\ge 3$。把一行的放置写成一个 $M$ 位掩码 $x$（第 $c$ 位为 1 表示该行第 $c$ 列放炮），则行内互不攻击等价于

前者排除列距 1，后者排除列距 2。这个条件只和 $M$ 有关，与地图内容和其它行完全无关。$M = 10$ 时满足它的掩码一共只有 60 个，可以一次性预计算。

地形是第二个过滤条件：必须 $x$ 的每个置位都落在平原上，即 $x \ \&\ \sim\text{plain}_i = 0$，其中 $\text{plain}_i$ 是第 $i$ 行的平原掩码。地形既不能阻挡攻击，也不制造跨行耦合，所以它只是"每行可选方案的一次过滤"，不必进状态。

第三步：行间约束只往前看两行。

第 $i$ 行与第 $j$ 行（$i < j$）的炮要冲突，必须同列且 $j - i \le 2$。行距恰好为 2（隔一行）也仍然攻击，这是本题最容易漏的一条。因此决定第 $i$ 行时，只有第 $i-1$、$i-2$ 行会产生限制，第 $i-3$ 行及更早已"过期"。

于是状态只需带上最近两行的列方案：

题面样例地图与每行的平原掩码如下（列 $c_0 \sim c_3$ 分别对应二进制字面量的最低位到最高位，即第 $c$ 列对应 1 << c）：

表的最后两列就是本题最关键的两张"零件表"：全 $M=4$ 只有 6 个行内合法掩码（0000、0001、0010、0100、1000、1001），再按每行地形过滤后每行只剩 3～6 个。第 2 行因 HH 丢掉 0100/1000/1001，第 5 行只剩 4 个——先把每行的方案表压小，后面的枚举才便宜。

第四步：转移。

第 $i+1$ 行要选 $z$，它必须同时满足四条约束：行内合法（$z \,\&\, (z \ll 1) = 0$ 且 $z \,\&\, (z \ll 2) = 0$）、不落山地（$z \,\&\, \sim\text{plain}_{i+1} = 0$）、与第 $i$ 行不同列（行距 1，$z \,\&\, x = 0$）、与第 $i-1$ 行不同列（行距 2，$z \,\&\, y = 0$）。前两条已经在"该行可选方案"里过滤过了，所以转移里只剩后两条，它们可以合并成一条

这里不需要检查 $x$ 与 $y$ 本身：它们的行距也是 1 或 2，但那一对约束在生成状态 $(x,y)$ 的那一步（也就是上一轮转移）就已经检查过了。正因为历史约束被"逐步消费"掉了，状态里只留两行才不会漏。

同一个键 $(z, x)$ 可能被多个不同的 $y$ 更新，取其中的最大值。下面是样例地图前两层真实算出的值（键写成 ($x$, $y$)，值是该键下前 $i$ 行的最大炮数）：

对照 (0010, 1001)=3 这一行：第 2 行 0010（列 2）与第 1 行 1001（列 1、4）按位与为 0，所以这一步合法，值就是 $\operatorname{popcount}(0010) + 2 = 3$。

第五步：初始值与答案。

第 1 行没有上一行，让它带着 $y = 0$（空掩码）入场：$f_{1,x,0} = \operatorname{popcount}(x)$。空掩码与任何掩码按位与都是 0，所以这一步不需要额外分支。

答案是 $\max_{x,y} f_{N,x,y}$。本题的两行状态记录的是已完成的历史（哪里已经放过炮），不像"竖牌向下伸出"那样欠下一行的账，所以最后不需要限定某个特定键，直接取全表最大值。

样例推演。 样例答案 6，一组达到 6 的方案是 $(1,1),(1,4),(2,2),(3,3),(4,1),(4,4)$：第 1 行放 2 门（同一行列 1 与列 4 相差 3，自身合法）；第 2、3 行各放 1 门，都落在前面两行没占的列上；第 4 行再放 2 门（列 1 与列 4 自身合法，且都不落在第 2 行的 $\{2\}$、第 3 行的 $\{3\}$ 上）。第 5 行 PHHP 只有 $c_1, c_4$ 是平原，而列 1、列 4 在第 4 行刚放过炮（行距 1），所以第 5 行只能空着，总数 $2+1+1+2+0=6$。

作为对照，用哈希表存状态时的逐层规模是：第 1 行 5 个状态（含 1001 这种一行两门炮的情形），到第 4 行涨到 22 个，第 5 行因地形受限收缩回 13 个，而各层最大值依次为 $2, 3, 4, 6, 6$。只遍历真实存在的 $(x,y)$ 组合，比 $1024 \times 1024$ 的空表格省得多。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 炮兵阵地：逐行推进的状态压缩 DP，键是 (本行列方案 x, 上一行列方案 y)。
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

typedef long long ll;

const ll SPREAD = 2; // 一门炮沿行、沿列都攻击左右各 SPREAD 格

ll width;
std::vector<ll> legal; // 一行内部互不攻击的列方案

// 一行内部互不攻击的列方案 x：两炮列距为 1 或 2 时会互相攻击
void build_legal() {
    legal.clear();
    for (ll x = 0; x < (1LL << width); x++) {
        if ((x & (x << 1)) == 0 && (x & (x << 2)) == 0) legal.push_back(x);
    }
}

ll popcount_ll(ll x) {
    ll c = 0;
    while (x) {
        c += (x & 1);
        x >>= 1;
    }
    return c;
}

int main() {
    ll n;
    if (scanf("%lld %lld", &n, &width) != 2) return 0;
    build_legal();

    // 题面每行可能连写，也可能逐字符用空格分隔，统一拼成一串再按行切
    std::string flat;
    std::string tok;
    while (std::cin >> tok) flat += tok;
    std::vector<std::string> rows(n);
    for (ll i = 0; i < n; i++) rows[i] = flat.substr(i * width, width);

    ll S = 1LL << width;
    std::vector<ll> cur(S * S, -1), nxt(S * S, -1); // 值 = 已决策行里最多放了多少炮
    std::vector<int> keys;

    // 每行的平原掩码与真正可选的列方案集合
    std::vector<std::vector<ll> > allowed(n);
    for (ll r = 0; r < n; r++) {
        ll plain = 0;
        for (ll c = 0; c < width; c++) {
            if (rows[r][c] == 'P') plain |= 1LL << c;
        }
        for (size_t t = 0; t < legal.size(); t++) {
            if ((legal[t] & ~plain) == 0) allowed[r].push_back(legal[t]);
        }
    }

    // 第 0 行没有上一行，用 y = 0 代表这一层约束不存在
    for (size_t t = 0; t < allowed[0].size(); t++) {
        ll x = allowed[0][t];
        cur[x * S + 0] = popcount_ll(x);
        keys.push_back((int)(x * S + 0));
    }

    for (ll r = 1; r < n; r++) {
        for (ll t = 0; t < S * S; t++) nxt[t] = -1;
        std::vector<int> nkeys;
        for (size_t a = 0; a < keys.size(); a++) {
            ll x = keys[a] / S, y = keys[a] % S;
            ll total = cur[keys[a]];
            ll blocked = x | y; // 本行、上行的炮位
            for (size_t c = 0; c < allowed[r].size(); c++) {
                ll z = allowed[r][c];
                if (z & blocked) continue; // 同列即纵向距离 ≤ SPREAD，冲突
                ll nk = z * S + x;
                ll cand = total + popcount_ll(z);
                if (cand > nxt[nk]) {
                    if (nxt[nk] < 0) nkeys.push_back((int)nk);
                    nxt[nk] = cand;
                }
            }
        }
        cur.swap(nxt);
        keys.swap(nkeys);
    }

    ll ans = 0;
    for (size_t a = 0; a < keys.size(); a++) {
        if (cur[keys[a]] > ans) ans = cur[keys[a]];
    }
    printf("%lld\n", ans);
    return 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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:19
# update_at: 2026-10-01 21:19

import sys

SPREAD = 2  # 一门炮沿行、沿列都攻击左右各 SPREAD 格；攻击不受地形阻挡


def legal_columns(width: int) -> list[int]:
    """一行内部互不攻击的列方案 x：两炮列距为 1 或 2 时会互相攻击。"""
    return [x for x in range(1 << width) if not x & (x << 1) and not x & (x << 2)]


def advance(states: dict[tuple[int, int], int], allowed: list[int]) -> dict[tuple[int, int], int]:
    """枚举当前行的合法列方案，把状态键从 (本行 x, 上一行 y) 推进到 (新行 z, 本行 x)。

    states 的值是「已决策的那些行里最多放了多少炮」；键用题解里的 (x, y) 符号，
    即本行、上一行的列占用方案，所以新行的候选变量也沿用题解的 z。
    """
    nxt: dict[tuple[int, int], int] = {}
    for (x, y), total in states.items():
        blocked = x | y  # 本行、上行的炮位；新行在这些列同列放置就会误伤
        for z in allowed:
            if z & blocked:  # 同列即纵向距离 ≤ SPREAD，冲突
                continue
            key = (z, x)
            total_here = total + z.bit_count()
            best_before = nxt.get(key, -1)  # 同一个键可能由不同的更早行到达
            if total_here > best_before:
                nxt[key] = total_here
    return nxt


def deploy(rows: list[str], width: int) -> int:
    """逐行推进的状态压缩 DP，返回全地图最多能部署的炮兵数。"""
    legal = legal_columns(width)
    # 每行的平原掩码：第 c 位为 1 表示该格是平原，可以放炮；山地格不能放
    plains = [sum(1 << c for c, cell in enumerate(row) if cell == "P") for row in rows]
    # 行内合法且不含炮位落在山地的方案，就是该行真正可选的列方案集合
    allowed = [[x for x in legal if not x & ~plain] for plain in plains]

    # 第 0 行没有上一行，用 y = 0（空掩码）代表这一层约束不存在
    states = {(x, 0): x.bit_count() for x in allowed[0]}
    for row_allowed in allowed[1:]:
        states = advance(states, row_allowed)
    return max(states.values())


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    try:
        n = int(next(it))
        width = int(next(it))
    except StopIteration:
        return
    # 题面每行可能连写，也可能逐字符用空格分隔，统一拼成一串再按行切
    flat = b"".join(it).decode()
    rows = [flat[i * width:(i + 1) * width] for i in range(n)]
    print(deploy(rows, width))


if __name__ == "__main__":
    solve()

复杂度

设 $M$ 为列数，$L$ 为行内合法掩码数（$M = 10$ 时 $L = 60$），$P$ 为"互不同列的两行掩码组合"数（$M = 10$ 时 $P = 2129$）。

• 时间：预处理 $O(2^M)$；每行枚举 $O(P \cdot L)$，共 $O(N \cdot P \cdot L)$。$M = 10$ 的粗略上界约 $1.3 \times 10^7$，而实际每层状态数远小于 $P$；地图中的山地会进一步压缩每行的可选方案。全 P 的 $100 \times 10$ 最坏数据实测约 0.44s / 16 MB，满足 1000ms、128MB 的限制。
• 空间：每层一个哈希表，键数 $O(P)$；另存每行可选方案 $O(N \cdot L)$。整体 $O(P + N \cdot L)$。

总结

• 先固定列方向：$N$ 大 $M$ 小（$N \le 100$、$M \le 10$）就是"按行推进 + 列方向状压"的信号，$2^M \le 1024$。
• 把行内合法性提前枚举掉：行内约束只由 $M$ 决定，$M = 10$ 时只剩 60 个合法掩码，比在转移里现场判断划算得多。
• 状态记住最近两行：因为同列且行距 $\le 2$ 都会攻击，行距 2 也不例外，所以两行记忆刚好够；更早的行约束已被逐步消费。
• 地形是过滤器，不是状态：它只影响每行"允许哪些方案"，不影响攻击传播，所以放在状态外面处理。
• 历史型状态取 $\max$：与"轮廓线/插头 DP"里需要收尾归零的状态不同，这里的末态没有欠账。

图示解析

状态推进路线

1
2
3
4
5
6N*M 网格（P/H）
`- 攻击 = 同行列距<=2 或 同列行距<=2（斜向不算）
   |- 行内约束只由 M 决定 -> 预计算 60 个合法掩码，再按地形过滤每行方案
   `- 行间约束只涉及最近两行 -> 状态 (本行 x, 上一行 y)
      |- 新行 z 满足 z & (x|y) == 0 才允许
      `- f[i+1][z][x] = max(..., f[i][x][y] + popcount(z)) -> 答案 max(f[N])

先看第一层如何把"十字攻击"化简成两个一维条件，再看状态为什么只需要两行，最后确认答案为什么不需要收尾约束。图中用 <= 做文本示意，正文中的严格表述是不等式 $\leqslant$。