C++轮廓线DP怎么逐格转移铺地砖方案数-C++-PHP中文网

轮廓线dp状态应定义为dppos，其中pos为当前处理格子编号（0≤pos

c++轮廓线dp怎么逐格转移铺地砖方案数

轮廓线DP状态怎么定义才对得上铺砖的“逐格”要求

轮廓线DP处理铺地砖（如1×2多米诺、L形三连块等）时，状态必须反映「当前决策格子左上方那条锯齿状边界」的覆盖情况——不是整行，也不是整列，而是从左到右、从上到下扫描时，紧贴已处理区域右侧的那条长度为 width + 1 的二进制轮廓线。每一位表示对应位置是否被上方/左侧伸过来的砖块「占用」（即该位置在轮廓线上方已覆盖，不可再放砖起始点）。dp[pos][mask] 中 pos 是当前处理的格子编号（0 ≤ pos height * width），mask 是长度为 width + 1 的整数，低位对应当前行最左列的上方状态。

转移时怎么判断能放哪几种砖、怎么更新mask

对每个 pos，先算出它在网格中的坐标：r = pos / width, c = pos % width。然后根据 mask 的第 c 位（表示该格正上方是否被占）和第 c+1 位（表示该格右侧邻居的「左边界」是否被占，实际用于判断横放砖能否向右延伸）决定可选动作：

若 mask 第 c 位为 0（上方没被占），可竖放一块1×2砖：新 mask 清除第 c 位，设置第 c+1 位（因为砖向下占了下一行同一列，影响下一行该列的「上方」状态）
若 c 且 <code>mask 第 c 位和第 c+1 位都为 0，可横放一块2×1砖：新 mask 清除第 c 和 c+1 位（本行这两列都被填满，不向下延伸）
若允许L形砖等复杂形状，还需检查 c+1 位及下一行对应位（需预取下一行的初始mask位），此时要额外维护「跨行依赖」，容易错位

关键细节：mask 每次转移后需右移一位（模拟扫描到下一格），但最高位由新放置行为决定；边界处（如 c == width - 1）不能横放，且第 width 位只用于承接上一行末尾的向下延伸，本身不对应真实列。

初始化和终态为什么必须用「全0 mask」且只在换行时清高位

第一格（pos=0）的初始 mask 必须是 0，表示整个上边界未被任何砖占用。当处理完某行最后一格（c == width - 1）后，若 mask 的第 width 位为 1，说明有一块竖砖从上一行延伸下来，它正好填满当前行最后一列——这是合法的；但此时要进入下一行，需把整个 mask 左移一位（丢弃第 width 位），并确保新 mask 最低位为 0（下一行首列上方无覆盖）。常见错误是忘记这一步左移，导致下一行首格误判为「上方已被占」。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

最终答案是 dp[height * width][0]，即所有格子处理完、轮廓线回归全空状态的方案数。若终态 mask ≠ 0，说明有砖伸出边界外，应舍弃。

内存和性能上哪些操作真不能省

轮廓线DP状态数是 O(height * width * 2^width)，width 超过 12 就极易爆内存。必须用滚动数组：只保留当前 pos 和 pos+1 两层 dp 表，且用 unordered_map<int long></int> 或 vector<long long></long>（索引为 mask）存非零项。别试图用 int 存方案数——稍大网格就会溢出。另外，位运算必须用 (mask >> c) & 1 判断第 c 位，而非 mask & (1 （后者在 <code>c 接近31时可能溢出 int）。