题意理解

我们有一个 $n \times m$ 的网格，包含两种格子：

. 表示打开的窗口（不需要覆盖）

. 表示关闭的窗口（需要覆盖）

规则：

胶带可以横向或纵向覆盖连续的关闭窗口

胶带不能经过打开的窗口（即不能跨过 .）

每个关闭窗口必须被恰好一卷胶带覆盖

胶带长度任意，宽度等于一个窗口的边长

目标：求覆盖所有 # 所需的最少胶带数量。

关键观察

1. 问题本质 这是一个 网格覆盖问题，类似于用最少的水平或垂直线段覆盖所有黑色格子，且线段不能跨过白色格子。

2. 列数小的提示 $m \leq 10$ 提示我们可以使用 状态压缩动态规划。

3. 覆盖方式分析 对于每个关闭的窗口，有两种覆盖方式：

横向覆盖：与同一行的连续 # 一起被覆盖

纵向覆盖：与同一列的连续 # 一起被覆盖

但注意：一个格子不能同时被横向和纵向胶带覆盖。

动态规划思路 状态设计 设 $dp[i][mask]$ 表示处理完前 $i$ 行，且第 $i$ 行的覆盖状态为 $mask$ 时的最小胶带数。

其中 $mask$ 是一个 $m$ 位的二进制数：

如果第 $j$ 位为 1，表示第 $i$ 行第 $j$ 列的格子被横向胶带覆盖

如果第 $j$ 位为 0，表示第 $i$ 行第 $j$ 列的格子被纵向胶带覆盖（或者该格子是 .）

状态转移 从 $dp[i-1][prev]$ 转移到 $dp[i][curr]$：

合法性检查：

如果网格 $(i,j)$ 是 .，则 $curr$ 的第 $j$ 位必须为 0（因为不能覆盖打开的窗口）

如果网格 $(i,j)$ 是 #，则 $curr$ 的第 $j$ 位可以是 0 或 1

计算当前行代价：

对于横向覆盖（$curr$ 中为 1 的位），如果形成连续的 1 段，每段需要 1 卷胶带

对于纵向覆盖（$curr$ 中为 0 且格子是 # 的位置），如果上一行对应位置也是纵向覆盖（$prev$ 对应位为 0），则不需要额外胶带；否则需要 1 卷胶带

转移方程

dp[i][curr]= prevmin {dp[i−1][prev]+horizontalCost(curr)+verticalCost(prev,curr)}

其中：

$\text{horizontalCost}(curr)$：当前行横向胶带数（连续 1 的段数）

$\text{verticalCost}(prev, curr)$：当前行新增的纵向胶带数

算法实现细节 预处理 预处理每个 $mask$ 的横向胶带数量

预处理合法的状态转移

初始化 $dp[0][0] = 0$，其他为无穷大

最终答案 $\min_{mask} dp[n][mask]$

复杂度分析 状态数：$O(n \times 2^m)$

转移：$O(2^m)$

总复杂度：$O(n \times 4^m)$

由于 $m \leq 10$，$4^m = 2^{20} \approx 10^6$，$n \leq 1000$，总操作数约 $10^9$，但实际常数较小，可以通过。

代码框架 cpp #include <bits/stdc++.h> using namespace std;

const int INF = 1e9; const int MAXN = 1005; const int MAXM = 10;

int n, m; string grid[MAXN]; int dp[MAXN][1 << MAXM]; int horizontal_cost[1 << MAXM];

int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> grid[i]; } for (int mask = 0; mask < (1 << m); mask++) { int cost = 0; for (int j = 0; j < m; j++) { if (mask >> j & 1) { cost++; if (j > 0 && (mask >> (j-1) & 1)) { cost--; // 连续段内不重复计数 } } } horizontal_cost[mask] = cost; } for (int i = 0; i <= n; i++) { for (int mask = 0; mask < (1 << m); mask++) { dp[i][mask] = INF; } } dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int prev = 0; prev < (1 << m); prev++) { if (dp[i-1][prev] == INF) continue; for (int curr = 0; curr < (1 << m); curr++) { // 检查状态合法性 bool valid = true; for (int j = 0; j < m; j++) { if (grid[i-1][j] == '.' && (curr >> j & 1)) { valid = false; break; } } if (!valid) continue; int vertical_cost = 0; for (int j = 0; j < m; j++) { if (grid[i-1][j] == '#' && !(curr >> j & 1)) { // 需要纵向覆盖 if (i == 1 || !(prev >> j & 1)) { vertical_cost++; } } } int total_cost = dp[i-1][prev] + horizontal_cost[curr] + vertical_cost; dp[i][curr] = min(dp[i][curr], total_cost); } } } int ans = INF; for (int mask = 0; mask < (1 << m); mask++) { ans = min(ans, dp[n][mask]); } cout << ans << endl; return 0; } 总结 这道题的核心是：

利用 $m$ 小的特点使用状态压缩DP

巧妙设计状态表示横向/纵向覆盖

仔细处理横向连续段和纵向连续段的计数

通过合理的状态设计和预处理，可以在规定时间内求解这个网格覆盖问题