Beautiful LucienElio!

问题分析#

首先，我们需要理解问题的核心。我们的目标是用最少的“真空清洁炸弹”清除所有灰尘。关键点在于：

1. 炸弹效果：一个炸弹可以影响其投放点及其上下左右四个相邻格子。
2. 影响范围：一个炸弹可能同时清洁多个污染区域（如果它们靠得很近）。
3. 灰尘清除：每个炸弹在其覆盖范围内，对每个污染区域只能清除 1 单位的灰尘。
4. 目标：清除所有区域的所有灰尘，求炸弹总数的最小值。

这个问题的难点在于，在某个位置投放炸弹的决策会影响到多个污染区域的清洁进度，而这些决策之间是相互关联的。例如，为了清洁A区域，我们可以在位置P投放炸弹，但这可能也顺带清洁了B区域的一部分灰尘，从而影响我们后续为B区域所做的决策。

由于污染区域的数量 $k$ 非常小（最多为 10），这是一个强烈的信号，暗示我们可以使用一种依赖于 $k$ 指数级复杂度的算法，而对 $n$ 和 $m$ 的依赖应该是多项式级的。这种问题类型通常指向状态压缩动态规划 (State Compression DP)。

算法核心：状态压缩 DP#

该代码采用的核心算法就是状态压缩 DP。让我们分解一下 DP 的要素：

代码逐段解析#

1. init() 函数

   • pows[i] = pows[i-1] * 4;: 计算 4 的幂，用于四进制状态表示。
   • memset(dp, 127, sizeof(dp));: 将 dp 数组初始化为一个极大值。127 在 int 类型中是一个非常大的正数。
   • dp[0] = 0;: 初始状态需要 0 个炸弹。

2. 主函数 main() - 输入和预处理

   • 读取 $n, m, k$。
   • 循环 $k$ 次读取每个污染区域的信息 x, y, w。
   • val[i] = w;: 存储第 $i$ 个区域的初始灰尘量。
   • ans += w * pows[i];: 计算并累加得到最终目标状态的整数表示。
   • for (int j = 0; j < 5; j++) ... mapp[{nt_x, nt_y}].push_back(i);: 这是预处理的关键。对于每个污染区域 i，它计算出能影响到它的 5 个炸弹投放点，并在 mapp 中记录下来。例如，要清理 (x,y) 的灰尘，可以在 (x,y), (x+1,y), (x-1,y), (x,y+1), (x,y-1) 这五个位置投弹。代码反过来想：在 (x+1,y) 投弹，可以影响到 (x,y)。

3. 主函数 main() - DP 核心循环

   • for (int i = 0; i < pows[k]; i++): 遍历所有可能的状态 i。这个循环的顺序保证了当我们计算 dp[a] 时，dp[i] 的值已经是最优的（这类似于 BFS 的思想）。
   • if (!check(i)) continue;: check(i) 函数用来剪枝。它检查状态 i 是否合法。一个状态是合法的，当且仅当对于每个污染区域，已清除的灰尘量不能超过其初始总量。例如，如果 val[0]=2，那么状态中第 0 位的值不能是 3。
   • for (auto j : mapp): 遍历所有有意义的炸弹投放位置。
   • int a = i;: 准备计算投放一次炸弹后的新状态。
   • for (auto o : tem) ... a += pows[o];: 计算新状态 a。check2(a, o) 确保我们不会为一个已经清理完毕的区域增加清理量。
   • dp[a] = min(dp[a], dp[i] + 1);: 执行 DP 状态转移。

4. 输出

   • cout << dp[ans];: 所有计算完成后，dp[ans] 就存储了达到最终目标状态所需的最少炸弹数。

样例 walkthrough#

输入: 5 5 3 1 1 2 (区域0) 2 2 1 (区域1) 5 5 2 (区域2)

• k=3, val[0]=2, val[1]=1, val[2]=2
• 目标状态 ans = $2 \cdot 4^0 + 1 \cdot 4^1 + 2 \cdot 4^2 = 2 + 4 + 32 = 38$。 我们要求 dp[38]。
• mapp 会包含类似这样的条目：
  • mapp[{1,2}] -> {0, 1} (在(1,2)投弹影响区域0和1)
  • mapp[{1,1}] -> {0, 1}
  • mapp[{2,2}] -> {0, 1}
  • mapp[{5,5}] -> {2}
  • … 等等

DP过程（简化示意）:

1. dp[0] = 0。
2. 从状态 0 出发，在 (1,2) 投弹。影响区域 0 和 1。新状态是 a = 0 + 4^0 + 4^1 = 5。dp[5] = min(inf, dp[0]+1) = 1。
3. 从状态 0 出发，在 (5,5) 投弹。影响区域 2。新状态是 a = 0 + 4^2 = 16。dp[16] = min(inf, dp[0]+1) = 1。
4. … 经过多轮迭代 …
5. 假设我们已经知道 dp 中某个状态 i 的值。例如，我们处于状态 i，再在 (1,2) 投弹一次。新状态 a 会在 i 的基础上，给区域 0 和 1 对应的位加 1。dp[a] = min(dp[a], dp[i] + 1)。
6. 最终，程序会找到一条到达目标状态 38 的最短路径。例如：
   • (0,0,0)_4 -> (1,1,0)_4 [在(1,2)投弹1次] -> (2,1,0)_4 [在(1,2)投弹1次] -> (2,1,1)_4 [在(5,5)投弹1次] -> (2,1,2)_4 [在(5,5)投弹1次]。
   • 状态路径 (十进制): 0 -> 5 -> 9 -> 25 -> 38
   • 炸弹数：1, 2, 3, 4。
   • 所以 dp[38]=4。

这个方案对应于在 (1,2) 投 2 枚炸弹，在 (5,5) 投 2 枚炸弹，总共 4 枚。

总结#

该解法是一个非常经典的状态压缩 DP 应用。它巧妙地将各个污染区域的清理进度压缩成一个整数状态，然后通过模拟投放炸弹这一动作，在状态之间建立转移关系，最终求得达到目标状态的最小代价（炸弹数）。预处理 mapp 极大地优化了状态转移的效率，避免了在庞大的网格上进行无效搜索。

关键理解：

• $ans$是目标状态，$dp[ans]$就是清除所有灰尘所需的最少炸弹数

完整代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 1e3 + 5, MAXN = 1049000; // 最大是 4^10
4

5
map<pair<int, int>, vector<int>> mapp;
6
// 用来存储图的信息：每个位置能影响的污染区域
7

8
int py[5][2] = {{0, 0}, {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
9
// 偏移量：自身及上下左右四个方向
10
int n, m, k, pows[15], ans, val[N], dp[MAXN];
11
// n,m,k 作用如题面，pows 用于存 4 的幂次，ans 用来记录目标状态
12
// val 是每个污染区域的灰尘数量
13

14
bool check(int x)
15
{
16
    // 检查状态x是否有效
17
    for (int i = 0; i < k; i++)
18
    {
19
        // 1. 获取第 i 位的值
20
        // x % 4 取出当前 x 最右边（最低位）的四进制位。
21
        // 在第 i 次循环中，这对应于第 i 个污染区域。
22
        if (x % 4 > val[i])
23
            return 0; // 0 在C++中代表 false
24

25
        // 2. 准备检查下一位
26
        // x /= 4 整数除法，相当于将四进制数向右移动一位，
27
        // 把刚刚检查完的位去掉，让下一位成为新的最低位。
28
        x /= 4;
29
    }
30
    // 3. 如果循环正常结束，说明所有位都合法
31
    return 1; // 1 代表 true
32
}
33

34
bool check2(int x, int y)
35
{
36
    // 检查第y个污染区域是否还有剩余灰尘
37
    // 1. 定位到第 y 位
38
    // 通过 y 次除以4的操作，将原先的第 y 位移动到最低位。
39
    for (int i = 0; i < y; i++)
40
        x /= 4;
41

42
    // 2. 获取第 y 位的值并比较
43
    // 此时 x % 4 就是原来第 y 个区域的已清除灰尘量。
44
    // 如果它等于初始量 val[y]，说明已经满了。
45
    if (x % 4 == val[y])
46
        return 0; // 返回 false，表示“满了，不能再加了”
47

48
    // 3. 如果没满
49
    return 1; // 返回 true，表示“没满，可以继续清理”
50
}
51
void init()
52
{
53
    pows[0] = 1;
54
    for (int i = 1; i < 11; i++)
55
        pows[i] = pows[i - 1] * 4;
56
    memset(dp, 127, sizeof(dp));
57
    dp[0] = 0;
58
    // 预处理
59
}
60

61
signed main()
62
{
63
    init();
64
    cin >> n >> m >> k;
65

66
    for (int i = 0; i < k; i++)
67
    {
68
        int x, y, w;
69
        cin >> x >> y >> w;
70
        val[i] = w;
71
        ans += w * pows[i];
72

73
        // 预处理所有能影响第i个污染区域的炸弹位置
74
        for (int j = 0; j < 5; j++)
75
        {
76
            int nt_x = x + py[j][0], nt_y = y + py[j][1];
77
            // 更新图的信息，把当前点能干涉到的点全部加上它
78
            mapp[{nt_x, nt_y}].push_back(i);
79
        }
80
    }
81

82
    // 状态压缩DP
83
    // 1. 遍历所有可能的状态
84
for (int i = 0; i < pows[k]; i++)
85
{
86
    // 2. 检查当前状态的合法性 (剪枝)
87
    if (!check(i))
88
        continue;
89

90
    // 如果状态 i 合法，尝试从状态 i 出发，投放一枚炸弹
91

92
    // 3. 遍历所有有效的炸弹投放位置
93
    for (auto j : mapp)
94
    {
95
        // 4. 计算投放这枚炸弹后会达到的新状态 a
96
        vector<int> tem = j.second; // 获取该炸弹能影响的区域列表
97
        int a = i; // 新状态 a 的基础是当前状态 i
98

99
        for (auto o : tem) // 遍历所有受影响的区域 o
100
        {
101
            // 如果区域 o 还没被清理完
102
            if (!check2(a, o)) // 注意这里检查的是 a 而非 i
103
                continue;
104
            // 那么就在新状态 a 中，将区域 o 的清理量+1
105
            a += pows[o];
106
        }
107

108
        // 5. 更新到达新状态 a 的最小炸弹数
109
        dp[a] = min(dp[a], dp[i] + 1);
110
    }
111
}
112
    cout << dp[ans];
113
    return 0;
114
}