1. 先看清楚题目限制再动手设计状态做状压DP绕不开的题P2704炮兵阵地算一个。这题来自NOI2001现在很多OJ上还能搜到标签基本都写着“状压dp”。题意一句话在一个N行M列的棋盘里放炮兵山地不能放每个炮兵能打到前后左右各两格的范围问最多能放多少个。N最大100M最大10。第一眼容易想搜索但很快就会发现状态空间大到离谱。这道题特别适合刚学状态压缩、想练滚动数组优化、以及准备省选级DP的人。我当年第一次写数组开错、初始化也错对着样例调了整整一晚上所以这次把整个推导过程和实战心得完整写出来。1.1 题意、数据范围与攻击范围先说输入。第一行两个整数N和M接下来N行每行一个长度为M的字符串里面只有两种字符P表示平原可以放炮兵H表示山地不能放。M不超过10N可以到100这个“列少行多”的结构几乎是给状压DP量身定做的。很多新手会问为什么不能用普通搜索如果直接枚举每一行放不放炮兵一行有2^M种可能M10时是1024但行数是100理论上要枚举1024^100种方案这肯定不行。还有个好多人会踩的坑炮兵的攻击范围到底怎么算。题目说是“前后左右各两格”这是一个十字形范围不是曼哈顿距离不超过2的圆。也就是说同一行内两个炮兵不能放在相邻列也不能隔一个列列差至少为3上下相邻的两行同一列不能同时放炮兵上下隔一行的两行同一列同样不能同时放炮兵如果两个炮兵一个在上一行第1列、一个在下一行第2列虽然斜着看距离很近但不在上下左右的十字范围里所以是安全的。这一点特别关键因为很多网上题解写得含糊会导致你误以为跨行时相邻列也要禁止。标准的做法里跨行冲突只用“两个状态按位与为0”来判断背后依据的就是“只有同一列会互相打到”。你要是一开始理解成曼哈顿距离后面写出来的转移条件就会多卡一堆本不该卡的状态虽然小数据也能过但看着代码总觉得哪里不对。1.2 为什么搜索和普通区间DP都走不通先算一笔复杂度账。如果直接DFS按行决策每行有1024种原始放置方案还要过滤山地形和行内冲突但最坏情况下每一行可能仍有一堆合法状态。N100时哪怕每行只有60种合法状态暴力组合也是60^100根本跑不完。所以必须把“之前行对当前行的限制”压缩成有限维状态让转移只依赖最近几行这就是状压DP的动机。那为什么只依赖最近两行因为炮兵能打到上下两格所以当前行的放置只会和上一行、上上一行冲突更早的行完全不影响现在。这给了我们一个漂亮的性质只需要记录“上一行状态”和“上上一行状态”再加上当前行状态就能完成转移。这有点像记忆化搜索里只保留必要的历史信息把指数级方案折叠成多项式级状态。普通区间DP也做不了。这里的约束不是“区间内最优”而是行与行之间的摆放互相牵制并且行数很长、列数很短天然适合按行推进。所以一看到N大M小列数小于等于10就应该立刻意识到每一行的部署都可以压缩成一个二进制整数然后用位运算判断冲突。这就是这道题的全部核心。2. 把一行压成一个数状态设计和转移方程2.1 把一行地形和一行部署都写成二进制状压的第一步就是把“放没放炮兵”编码成一个整数。M10时用一个int的低10位就够了。从右往左第j位表示第j列位为1表示这一列放炮兵0表示不放。比如0001001001这样的二进制数就代表第0列、第3列、第6列各放了一个炮兵。地形也可以用同样的方式编码。我习惯把山地的位置设成1平原设成0。读入字符串的时候如果第j个字符是H就在hill[r]这个整数里把第j位设为1。判断一个状态s能不能放在第r行只需要看(s hill[r])是否为0如果某一位同时是1说明炮兵放到了山地上直接淘汰。反过来把平原记为1、山地记为0也能做但后面判断就要写(s hill[r]) s我个人觉得容易写错所以更推荐“山地为1”的写法。2.2 行内合法状态为什么只剩60个单纯把一行压成二进制还不够因为1024种原始状态里绝大多数在单行内就已经违规了。比如0000000011代表第0列和第1列各放一个炮兵这两个炮兵在同一行且相邻显然会互相攻击。还有0000000101代表第0列和第2列各放一个列差为2也在攻击范围内同样非法。行内合法的检查非常简洁if ((s (s 1)) 0 (s (s 2)) 0) { // s 是单行合法状态 }解释一下。s1相当于把s里的每个1都往左挪一位如果s原来在相邻位置有两个1那么挪过去之后它们会重叠s (s1)就不是0。同理s2检查距离为2的两个1。这两个条件合起来就保证了同一行内任意两个1之间的列差至少为3。这里有个细节只需要左移检查不需要再检查右移因为(s (s1))已经覆盖了所有相邻对左移和右移判断的是同一个关系。过滤之后还剩多少状态对于M10我算过单行合法状态恰好在60个左右。这个数字可以这样直观理解长度为n的一行合法摆放数满足一个类似斐波那契的递推。最后一位不放时前面n-1位可以随便合法最后一位放时倒数第二、第三位都必须空出来所以只取决于前面n-3位。按这个递推从n1算到n10得到的就是60。你不需要背这个数只需要知道1024个原始状态经过行内过滤规模缩小到60这直接让后面的DP从“完全不可做”变成“轻松可做”。把60个状态存进数组后还要顺手把每个状态里1的个数算出来这就是这一行的炮兵数量。C里用__builtin_popcountPython里可以用bin(s).count(1)也可以预处理一张数量表后面每次转移都要用到。2.3 跨行兼容规则与三层状态的转移行内合法只解决了一行自己的问题跨行冲突才是这个题的核心。前面说过炮兵上下能打两格所以当前行状态cur、上一行状态prev、上上一行状态prev2之间只要任意两个状态在某一列上同时为1就说明有两个炮兵在同一列且行差不超过2这样会互打。判断方法就是按位与if ((cur prev) 0 (cur prev2) 0)这里不用再单独检查prev prev2因为当上一行作为“当前行”被填入DP时已经保证过它和上上行不冲突。递推过程中始终保持的约束就是任意连续三行状态两两不冲突。那么DP数组怎么设计最直观的是三维数组dp[i][j][k]表示处理到第i行且第i行状态为j、第i-1行状态为k时前i行最多能放多少炮兵。转移的时候枚举第i-2行的状态l看j、k、l是否互相兼容。转移方程写出来就是dp[i][j][k] max(dp[i-1][k][l] cnt[j])其中要求(j k) 0、(j l) 0而(k l) 0在之前已经成立。cnt[j]是状态j中炮兵的个数。为什么只需要三层因为炮兵最多影响上下两行所以第i行放多少只和第i-1行、第i-2行有关。一旦处理完第i行第i-2行就不再需要被记住。这就像一个滑动窗口窗口大小是3行每推进一行就丢掉最早的那行。这也是滚动数组能用的根本原因我们永远只需要保留上一轮的两层状态就够了。2.4 边界处理第0行和第1行怎么初始化边界问题往往是新手翻车最严重的地方。用滚动数组递归地写边界反而可以统一处理在真正的第一行之前假设上一行和上上行都是空状态0。因为空状态和任何状态都不冲突也不占地更不影响答案。这样每一行都走同一个转移流程不需要单独写“第0行怎么初始化、第1行怎么初始化”的特判。DP数组初始化为dp[0][0] 0其他全部是-1。这里的两个下标分别表示“上一行状态编号”和“上上一行状态编号”一开始都指向0号空状态。由于预处理状态是从0开始递增枚举的0号状态一定是空状态0。这个前提很关键如果你乱序生成状态表就一定要先找到0的下标不然初始化就错了。处理第0行时cur会和prev0、prev20做按位与结果都是0所以只要cur不落在山地就能直接由dp[0][0]cnt[cur]转移到新数组。处理第1行时prev是第0行状态prev2是空状态同样不需要特殊分支。也就是说用-1和0号空状态配合整个N行的循环体可以写得非常统一这个技巧在不少状压DP里都适用。3. 完整C实现与逐段解释3.1 预处理地形掩码、合法状态、炮兵数量下面这个版本是我在OJ上实际提交过、也验证过的C17可以直接用。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; vectorint hill(N, 0); for (int i 0; i N; i) { string s; cin s; for (int j 0; j M; j) { if (s[j] H) { hill[i] | (1 j); } } } vectorint st, cnt; for (int s 0; s (1 M); s) { if ((s (s 1)) 0 (s (s 2)) 0) { st.push_back(s); cnt.push_back(__builtin_popcount(s)); } } int S (int)st.size(); vectorvectorint dp(S, vectorint(S, -1)); vectorvectorint ndp(S, vectorint(S, -1)); dp[0][0] 0; for (int r 0; r N; r) { for (int i 0; i S; i) { fill(ndp[i].begin(), ndp[i].end(), -1); } for (int i 0; i S; i) { int cur st[i]; if (cur hill[r]) continue; for (int j 0; j S; j) { int prev st[j]; if (cur prev) continue; for (int k 0; k S; k) { if (dp[j][k] 0) continue; int prev2 st[k]; if (cur prev2) continue; int val dp[j][k] cnt[i]; if (val ndp[i][j]) { ndp[i][j] val; } } } } dp.swap(ndp); } int ans 0; for (int i 0; i S; i) { for (int j 0; j S; j) { ans max(ans, dp[i][j]); } } cout ans \n; return 0; }这段代码有两个容易写错的位置。第一个是dp[0][0] 0前面必须确认st[0] 0。我从for (int s 0; ...)开始枚举0是合法状态所以它一定在数组第一个位置。第二个是每轮循环前要把ndp整个填成-1而不是只改几个用到的位置。如果你漏掉重置上一轮的旧值会残留在新数组里转移时会拿到一堆脏数据答案就莫名其妙偏大。3.2 滚动数组DP主循环滚动数组的核心就是dp和ndp两个二维数组反复交换。每一轮ndp的ndp[i][j]表示当前这一行用状态i、上一行用状态j时前r1行的最大炮兵数。上一行的状态j来自旧dp的第一维上上一行的状态k来自旧dp的第二维因此dp[j][k]直接对应“上一行是j、上上行是k”的旧结果。转移有三个门槛要过cur hill[r]为0说明当前状态不在山地上cur prev为0说明当前行和上一行不在同一列放炮兵cur prev2为0说明当前行和上上行不在同一列放炮兵。三个门槛都过了才能用dp[j][k] cnt[i]去更新答案。细心的读者会问为什么不检查prev prev2因为dp[j][k]本身是在上一轮由j和k合法组合得到的如果j和k不兼容这个DP位置永远是-1根本进不了后面的更新。所以这里确实是省事的不是漏了。循环顺序上i、j、k三层枚举全部在S范围里S最大60三层最坏就是606060216000种组合再乘N100也就2000万次左右的位运算和比较。这个复杂度对C来说连优化都不用刻意做直接跑就能过。3.3 答案统计与常见输出坑处理完所有行以后答案怎么取很多新手会写dp[S-1][S-1]其实最后一行不一定用编号最大的状态最后一行的上一行也不一定。正确做法是遍历整个dp数组把所有不是-1的位置取最大值。还有一个坑如果整个棋盘全是山地或者地形限制导致一行都放不了DP数组里只有dp[0][0]从初始0慢慢滚到最后一轮还是0答案输出0完全正确。但如果初始化写错了比如把dp[0][0]写成1那答案就会变成1这就是典型的边界污染。所以我建议提交前故意构造一个全H的用例跑一下输出应该是0。4. Python参考实现与提速细节4.1 一个能跑的Python兼容表实现Python写这个题时间复杂度会比较紧张但并不是不能写。关键是要把“两个状态是否兼容”预先算成一张表避免在循环里反复做位运算。下面这个版本我用来做小数据验证和教学演示是没问题的PyPy下跑极限数据有机会通过CPython会比较吃力。import sys def solve(): input sys.stdin.readline N, M map(int, input().split()) hill [] for _ in range(N): s input().strip() mask 0 for j, ch in enumerate(s): if ch H: mask | (1 j) hill.append(mask) states [] pc [] for s in range(1 M): if (s (s 1)) 0 and (s (s 2)) 0: states.append(s) pc.append(bin(s).count(1)) S len(states) compat [] for i in range(S): row [] for j in range(S): if (states[i] states[j]) 0: row.append(j) compat.append(row) dp [[-1] * S for _ in range(S)] dp[0][0] 0 for r in range(N): cur_idx [i for i, s in enumerate(states) if (s hill[r]) 0] ndp [[-1] * S for _ in range(S)] for i in cur_idx: cur_compat compat[i] cur_cnt pc[i] for j in cur_compat: dpj dp[j] for k in cur_compat: if dpj[k] 0: val dpj[k] cur_cnt if val ndp[i][j]: ndp[i][j] val dp ndp print(max(max(row) for row in dp)) if __name__ __main__: solve()这段代码里compat[i]存的是所有和状态i按位与为0的状态编号。转移时枚举j和k都只在cur_compat里枚举等于提前过滤掉了所有“当前行和上一行冲突”“当前行和上上行冲突”的组合比三层盲扫快不少。4.2 三种提速手段兼容表、行候选表、PyPyPython版本能过依赖三个提速点。第一是兼容表把states[i] states[j] 0这种结果缓存成列表省去内层频繁的位运算。第二是行候选表cur_idx每一行只枚举不落在山地上的状态山地多的时候加速特别明显。第三是运行环境PyPy对纯循环代码的优化比CPython好很多同样的逻辑用PyPy跑速度能差好几倍。如果还想再快一点可以把二维dp展平成一维数组用dp[j * S k]代替dp[j][k]。这个改动会降低Python列表索引的开销但代码可读性会下降。我的建议是如果你只是想学会算法用上面这个版本理解就够了如果你真想用Python去冲极限OJ那就老老实实把关键循环改成C或者至少用PyPy提交。5. 实战中踩过的坑调试与对拍5.1 五个最隐蔽的错第一个错误把山地的bit位顺序搞反。比如输入字符串第一个字符是左边还是右边不同人的习惯不同。只要你在读入时统一处理其实无所谓但一旦一会儿按正序、一会儿按倒序后面位运算就会乱。我建议固定成“字符串从左到右对应二进制低到高位”写注释标清楚。第二个错误行内冲突没考虑隔两格。只用(s (s 1)) 0会把距离为2的炮兵漏掉答案偏大。第三个错误跨行冲突想当然写成曼哈顿距离于是多加了相邻列判断导致本该合法的状态被丢掉答案偏小。第四个错误滚动数组没重置。旧数据残留会让答案异常偏大而且只在某些数据上出现特别难查。第五个错误初始下标想当然。如果状态表不是从0开始枚举或者把空状态排到了别的位置dp[0][0]0就会初始化到错误的地方最后结果全乱。这里给一个自查用的经验先用样例数据跑得到正确答案后把DP数组在每一行结束时的最大值打印出来肉眼确认它是否单调不减。因为每多一行至少可以保持上一行的放置不动所以答案不应该变小如果变小了基本就是滚动数组重置或者状态枚举出了问题。5.2 怎么用小数据对拍和肉眼验证对拍是排查状压DP错误最有效的手段。M很小的时候比如N最多6、M最多5可以直接写一个暴力深搜枚举所有方案和状压DP的答案做对比。暴力搜索的思路是逐行逐列尝试放炮兵每放一个就检查它和已放炮兵是否冲突。数据量小的时候暴力是绝对正确的因为它就是按题意的字面规则模拟。对拍流程很简单写一个数据生成器随机生成N和M随机生成P/H地形跑一遍暴力程序得到ans1再跑一遍状压DP程序得到ans2两边不一致就停下来把当前这组数据打印出来人工检查。通常不一致的用例都会很小比如4行5列一眼就能看出是哪一行状态被多算了或者少算了。这个流程能覆盖掉上面说的绝大多数错误。还有一个小技巧把合法状态表打印出来和手算的对比。M3时合法状态应该是0、1、4、5这四种。M4时是0、1、2、4、5、8、9、10一共8种。如果你打印出来的数量和组合不对那说明行内过滤条件写错了这种错在DP之前就会污染全局。6. 复杂度小结与同类题经验6.1 时间复杂度别只记O(N*S^3)很多人背这个题的时间复杂度只背一个O(N*S^3)其中S是单行合法状态数。这样记没错但不够。关键在于S的上限M10时S是60所以60^3 * 100大约是2160万次操作这是非常宽裕的。可如果题目把M改成15单行合法状态数会涨到三位数S^3就非常恐怖原来的做法直接超时。所以看到M10心里要立刻反应出“合法状态只有几十个”这个结论而不是只知道套板子。空间复杂度也要清楚。不滚动的话dp[N][S][S]就是1006060大概360000个整数很小滚动数组后变成26060理论上更省。但滚动数组不是免费的它要求你写对数组重置逻辑。我的建议是如果N只有100哪怕不滚动也完全没问题新手可以先用三维数组把思路写顺再改成滚动数组优化。反过来有些题N很大三维数组会爆内存那时候滚动数组就是必须的。6.2 这类题的后劲炮兵阵地是“三行关联”状压DP的代表做完它再去看其他状压题会发现套路是相通的。比如有的题只要求相邻行互不干扰那只需要记录上一行状态二维DP就够有的题要求八个方向互不攻击那需要处理斜向冲突但状态压缩和位运算判冲突的思路不变还有的题是轮廓线DP一行一行推变成一格一格推状态从行状态变成轮廓状态。核心都是把局面压缩成整数用位运算快速判断合法性然后按行或按格转移。我自己做这类题的经验是遇到N大M小的棋盘先别急着写代码先花五分钟把三件事想清楚单行合法状态怎么筛、跨行限制最多往前看几行、DP数组每个维度分别代表什么。这三件事想明白了剩下就是套板子的事。炮兵阵地这道题之所以经典就是因为它刚好把这三个问题都展示了一遍。你把这题吃透后面遇到再奇怪的棋盘限制也都能往这个框架里套。