信息学奥赛算法练功房◌检测中
题单　·　习题解析

洛谷 P2704 炮兵阵地

★★★ 真正的关卡是内存：不筛合法行 400 MB（题面给 128）；⚠⚠ 而我差点写下一个假的「精确的 0」——那一档 300 轮里只有 1 组不同的输入

原题：洛谷 P2704出自 第 28 章 状压 DP 入门：旅行商问题 的题单题面本地存档：2026-08-30
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库（原题那张攻击范围图也存了）。

转录自洛谷 P2704，日期见页头。两边不一致时信原站。

题目描述

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

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

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

P2704 炮兵的攻击范围：沿横向左右各两格、沿纵向上下各两格

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域： 沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。 从图上可见炮兵的攻击范围不受地形的影响。

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

输入格式

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

接下来的 N 行，每一行含有连续的 M 个字符，按顺序表示地图中每一行的数据。

输出格式

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

说明/提示

对于 100% 的数据，1 ≤ N ≤ 100，1 ≤ M ≤ 10，保证字符仅包含 P 与 H。

输入输出样例

输入

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出

6

5 × 4 的地图，最多摆 6 门炮。

⚠ 这一组样例只挡住了两个错法里的一个（只记前一行打出 8）—— 而「同行忘了隔两格」原样打出 6，放过了。

1★★ 关键的一步：状态要记「前两行」

★ 射程两格 ⇒ 第 i 行和第 i−2 行也会打架

上一道 P1896 里国王只影响相邻一圈，所以状态记住「上一行」就够了。 炮兵的射程是上下各两格 ⇒ 第 i 行和第 i−2 行也要互相避让 ⇒ 状态必须多带一行：

    f[i][a][b] = 前 i 行摆好、第 i 行摆法是 a、第 i−1 行摆法是 b 时，最多摆几门炮
    f[i][a][b] = max over c: f[i-1][b][c] + |a|
                 要求 a & b、a & c、b & c 全是 0

★ 同一行内也一样：横向射程两格 ⇒ 两门炮至少隔 3 格 ⇒ 合法行的判据是 (S & (S<<1)) == 0 且 (S & (S<<2)) == 0。

p2704.cpp★ 这一版就能 AC
// P2704 炮兵阵地 —— 正解：按行状压 DP ＋ 状态记**前两行**
//
// ★ 和前两道棋盘状压的差别只有一句话：**炮兵的攻击范围是上下各两格**
//   ⇒ 第 i 行能不能这么摆，取决于第 i−1 行**和第 i−2 行** ⇒ 状态要多带一行。
//
//   f[i][a][b] = 前 i 行摆好、第 i 行摆法是 a、第 i−1 行摆法是 b 时，最多能摆几门炮
//   f[i][a][b] = max over c: f[i-1][b][c] + |a|      要求 a&b、a&c、b&c 都是 0
//
// ★★ 而这道题真正的关卡是**规模**：m ≤ 10 ⇒ 2¹⁰ = 1024 个 S，
//    朴素状态数 n × 1024 × 1024 = 1 亿个 int = 400 MB，**装不下**（题面给 128 MB）。
//    出路是「先筛合法行」：同一行内相隔至少 3 格的摆法只有 **60** 个（见 Count 第 ⑤ 段）
//    ⇒ 状态数降到 n × 60 × 60 = 36 万，**内存差 2900 倍**。
//    ⇒ 这一次那个优化不是「好看」，是**能不能交**。
//
// ⚠ 输入是 P/H 字符，不是 0/1；山地不能放炮。


#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> plain(n + 1, 0);                       // 第 i 行哪些格子是平原（可以放）
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] == 'P') plain[i] |= 1 << j;
    }


    // ★ 先筛出「同一行内两两相隔 ≥ 3 格」的摆法
    vector<int> st, num;
    for (int S = 0; S < (1 << m); S++) {
        if ((S & (S << 1)) || (S & (S << 2))) continue;
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int K = (int)st.size();


    const int NEG = -1e9;
    vector<vector<int>> f(K, vector<int>(K, NEG)), g(K, vector<int>(K, NEG));
    // 第 1 行：上一行想象成空行（下标 0 那个状态一定是 S = 0）
    for (int a = 0; a < K; a++)
        if ((st[a] & ~plain[1]) == 0) f[a][0] = num[a];


    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), NEG);
        for (int a = 0; a < K; a++) {                  // 第 i 行
            if (st[a] & ~plain[i]) continue;
            for (int b = 0; b < K; b++) {              // 第 i−1 行
                if (st[a] & st[b]) continue;
                for (int c = 0; c < K; c++) {          // 第 i−2 行
                    if (f[b][c] <= NEG) continue;
                    if (st[a] & st[c]) continue;
                    g[a][b] = max(g[a][b], f[b][c] + num[a]);
                }
            }
        }
        f.swap(g);
    }


    int ans = 0;
    for (int a = 0; a < K; a++)
        for (int b = 0; b < K; b++) ans = max(ans, f[a][b]);
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

2★★★ 而这道题真正的关卡是内存，不是时间

★★ 不筛合法行就是 400 MB，而题面只给 128 MB

m ≤ 10 ⇒ 2¹⁰ = 1024 个 S。朴素状态数是 n × 1024 × 1024：

顶格 n = 100、m = 10
不筛合法行 100 × 1024 × 1024 × 4B = ★ 400 MB ⇒ 装不下（题面 128 MB）
先筛（合法行只有 60 个） 1 MB
再滚动成两层 ★ 28 KB
相差 ★ 291 倍

⇒ ★★★ 在上一道 P1896 上，「先筛合法行」还只是省时间（5.75 倍）； 在这道题上它是能不能交的问题。 ⇒ 这是本书那条「答案对但跑不完 / 装不下，只能靠算」的又一次现场 —— 样例和对拍都不会告诉你 400 MB 这件事。

★ 顺带一条能自己验的性质：合法行的个数随 m 是 2, 3, 4, 6, 9, 13, 19, 28, 41, 60 —— 它满足 a(m) = a(m−1) + a(m−3)， 是上一道那个斐波那契的三阶版本（那儿是隔 1 格，这儿是隔 2 格）。

3★ 两个错法，都是「少了一条限制」

p2704OneRow.cpp✗ 状态只记前一行
// ✗ P2704：状态只记了**前一行**（把 [P1896] 的写法搬过来）
//
// ★ 炮兵的射程是上下**各两格**，所以第 i 行和第 i−2 行也会打架 ——
//   只记一行的话，那条约束就没人管了。
// ⇒ 少了一条限制 ⇒ 它数出来的摆法**恒 ≥ 正解**。
// ⚠ 本轮第四次「上一道的正确写法就是这一道的 bug」。


#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> plain(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) if (s[j] == 'P') plain[i] |= 1 << j;
    }
    vector<int> st, num;
    for (int S = 0; S < (1 << m); S++) {
        if ((S & (S << 1)) || (S & (S << 2))) continue;
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int K = (int)st.size();
    const int NEG = -1e9;
    vector<int> f(K, NEG), g(K, NEG);
    for (int a = 0; a < K; a++) if ((st[a] & ~plain[1]) == 0) f[a] = num[a];
    for (int i = 2; i <= n; i++) {
        fill(g.begin(), g.end(), NEG);
        for (int a = 0; a < K; a++) {
            if (st[a] & ~plain[i]) continue;
            for (int b = 0; b < K; b++) {
                if (f[b] <= NEG || (st[a] & st[b])) continue;     // ← 只管了上一行
                g[a] = max(g[a], f[b] + num[a]);
            }
        }
        f.swap(g);
    }
    cout << *max_element(f.begin(), f.end()) << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
p2704NoGap2.cpp✗ 同行只判了「不相邻」
// ✗ P2704：同一行内只判了「不相邻」，忘了「隔一格也不行」
//
// ★ 横向射程也是两格 ⇒ 同一行里两门炮至少要隔 **3** 格（中间空 2 格）。
//   写成 `S & (S << 1)` 只挡住了「紧挨着」，还得加 `S & (S << 2)`。
// ⇒ 又是一个少了限制的超集 ⇒ 恒 ≥ 正解。
// ⚠ 而它顺带把合法行从 60 个放大到 144 个 —— 内存也跟着涨（见 Count 第 ⑤ 段）。


#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> plain(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) if (s[j] == 'P') plain[i] |= 1 << j;
    }
    vector<int> st, num;
    for (int S = 0; S < (1 << m); S++) {
        if (S & (S << 1)) continue;                    // ← 少了 S & (S << 2)
        st.push_back(S);
        num.push_back(__builtin_popcount((unsigned)S));
    }
    int K = (int)st.size();
    const int NEG = -1e9;
    vector<vector<int>> f(K, vector<int>(K, NEG)), g(K, vector<int>(K, NEG));
    for (int a = 0; a < K; a++) if ((st[a] & ~plain[1]) == 0) f[a][0] = num[a];
    for (int i = 2; i <= n; i++) {
        for (auto& r : g) fill(r.begin(), r.end(), NEG);
        for (int a = 0; a < K; a++) {
            if (st[a] & ~plain[i]) continue;
            for (int b = 0; b < K; b++) {
                if (st[a] & st[b]) continue;
                for (int c = 0; c < K; c++) {
                    if (f[b][c] <= NEG || (st[a] & st[c])) continue;
                    g[a][b] = max(g[a][b], f[b][c] + num[a]);
                }
            }
        }
        f.swap(g);
    }
    int ans = 0;
    for (int a = 0; a < K; a++) for (int b = 0; b < K; b++) ans = max(ans, f[a][b]);
    cout << ans << '\n';
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
300 轮（4 × 4，平原率 75%） ≥ 正解 被抓 样例挡住？
只记前一行（漏了「隔一行也打得到」） 300 / 300 109 ✅ 8 vs 6
同行只判不相邻（漏了「隔一格也打得到」） 300 / 300 103 ❌ 放过（6 vs 6）

⚠ 「只记前一行」又是一次上一道的正确写法就是这一道的 bug（P1896 那儿只记一行完全够）—— 本轮第四次。

4⚠⚠ 我差点写下一个假的「精确的 0」

★★★ 300 轮，其中只有 1 组不同的输入 —— 那个 0 是我自己造出来的

拧平原率这把旋钮时，最后一档的结果非常漂亮：

平原率（各 300 轮） 只记前一行 同行只判不相邻 ⚠ 300 轮里不同的输入有几组
40% 77 76 299
60% 115 110 299
80% 100 98 249
100% ★ 0 ★ 0 ⚠⚠ 1

差一点就写成「全平原时两个 bug 一起隐身，是结构性的 0」。 但那个 0 的真正原因是：平原率 100% 时所有种子造出的是同一张图 —— 300 轮其实只测了 1 组。

⇒ 自检很便宜：直接拿全平原的 k × k 一个个试：

全平原 k=3 k=4 k=5 k=6 k=7
正解 3 6 9 12 17
两个 bug 3 6 ★ 10 12 ★ 18

4×4 和 6×6 上它们恰好对，5×5 和 7×7 上就错了。 ⇒ 那个 0 是「只测了一组」，不是「bug 隐身」。

⇒ ★★★ 这条给本书那句老话添了一个新形态： 第 14 章 P1746 说过「一致有两种：都算对了，和都没算」； 这一次是第三种 —— 轮数是假的。 ⇒ 看到某一档掉到 0，先数一数那一档里到底有几组不同的输入。

★ 另外，抓获率沿平原率是单峰的（77 → 115 → 100 → …）—— 本书第三次量到单峰（第 13 章 P1596 沿密度、第 20 章 P1048 沿 T）。

5★ 参照物和规模
300 轮：正解 vs 2^(N×M) 逐格枚举 ★ 不一致 0 轮
顶格 n = 100、m = 10 状态 100 × 60 × 60，转移 O(60) ⇒ 约 2 × 10⁷ 次
答案上界 每行最多 ⌈10/3⌉ = 4 门 × 100 行 ⇒ int 绰绰有余
p2704Brute.cpp参照物：2^(N×M) 逐格枚举（300 轮不一致 0 轮）

6度量程序和生成器

p2704Count.cpp度量程序（本页所有数字都出自它）
p2704Gen.cpp数据生成器

7一页纸
★★ 关键的一步 射程两格 ⇒ 状态记前两行 f[i][a][b]；同行两门炮至少隔 3 格
★★★ 真正的关卡是内存 不筛合法行 400 MB（题面给 128）；筛完 1 MB、滚动 28 KB —— 291 倍
★ 只记前一行 超集 ⇒ 恒 ≥ 正解，被抓 109/300（样例挡住）
★ 同行只判不相邻 超集 ⇒ 恒 ≥ 正解，被抓 103/300（⚠ 样例放过）
⚠⚠ 差点写下的假结论 平原率 100% 那两个 0 是因为300 轮只有 1 组不同输入；全平原 5×5/7×7 照样错
★ 能自己验的性质 合法行个数 2,3,4,6,9,13,19,28,41,60 满足 a(m)=a(m−1)+a(m−3)
参照物 2^(N×M) 逐格枚举；300 轮不一致 0 轮