POJ1185炮兵阵地讲解稿
大家好，今天我想讲一讲炮兵阵地这道题。对于之前在一班上课的同学，这道题应该不会
陌生，这是我们最后一天上课的最后一题。
请大家再次阅读一下题面，之前在二班上课的同学请先审一下题。（朗读题面）
Description
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组
成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每
一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在
地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击
到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可
见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能
互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最
多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每
一行的数据。N <= 100；M <= 10。
Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
我们注意到数据范围是100*10的，也就意味着我们可以使用略微暴力一些的方法来解决这
个问题。再看输入输出的格式，输入的内容为PH构成的矩阵，输出只需要输出最优解的数量
即可。
我们应该如何解决这道题呢？
首先考虑读入，由于读入的数据全部都由P和H组成，我们可以开一个二维的char数组来储
存。当然，如果规定P和H为true和false，我们可以使用布尔类型来存储整个矩阵。如果我们
把矩阵的列去掉，事实上每一行就变成了一个二进制数，于是我们便能仅仅使用100个int数
来存储矩阵了。这就是我星期一的时候讲到的状态压缩。虽然看起来对空间需求的降低很有
限，但这样做的好处在后面的解题过程中将体现得很明显。
数据存入了之后我们很容易便能想到最暴力的做法：枚举放置哪些点，检查是否会出现非
法的状况。显然，在多数情况下，这个方法是会超时的。
我们可以把矩阵中抽出一行来看。对于一个全部都由P组成的行而言，炮兵的可行排布事实
上并不多。具体来说，要让一行合法，这一行中每一个炮兵左边两个和右边两个格子都不能有
炮兵。既然我们在存储的时候选择了用状态压缩来进行，不妨也把一行中合法的状态也压缩一
下。我们可以用1和0来表示是否有炮兵在相应的格子中。事实上，每个自然数的二进制表示
都代表着一种状态，所以我们只需要从0开始枚举每一个小于等于（1<<m）－1的整数就可以
了。为什么是（1<<m）－1呢，做一个简单运算就可以看出，取m为5的时候，1左移5位得
到的数是100000，再减去1就得到11111，也就是5位的二进制数的最大值。那么如何判断
是否合法呢？既然已经使用了状态压缩，肯定和二进制位运算脱不了关系。我们把一个状态对
应的二进制数左移一位，现在是1的地方就是这个状态下炮兵左边一格的攻击范围，此时为1
的位置在我们这个状态中绝对不能是1，否则会有可能误伤。如果我们把左移一位后的数和原
表示状态的数&起来，由于&运算是均为1则为1，所以只要有两个1出现在相同位置，&的结
果就一定大于零，反之，只要结果为0，就代表每个炮兵的左边一格不会误伤盟友。同理，再
把状态对应的二进制数分别左移两位，右移一位，右移两位后的结果与原状态的数来进行&运
算，如果都是0，则说明这个单行状态是合法的。我们用一个数组zt来记录下所有的合法状态
并重新编号。同时，最好还要记录一下每一个zt数组中的值在二进制表示下1的个数，这个的
计算与星期一讲的快速幂很类似，请大家自己完成代码，如果写不出也可以课后来问我。当
然，我们也可以直接枚举出10位以内的所有合法状态打成一个表，预先插入到程序内，再计
算出每一个m对应的最大整数值(1<<m)-1记录到ky数组即可。要特别注意，在写带有位运算
的表达式时，由于位运算的优先级最低，故一定要根据运算需要打足括号，否则会出现一些意
想不到的问题。
做完这一步，你或许可以长舒一口气，但不要着急，这还只是整个程序的预处理部分，真
正的算法还在后面。不过如果理解了前半部分，后面的算法实现应该不难掌握。
既然搜索不成，我们可以考虑使用动态规划来解决这个问题。能否用一维来解决问题呢？
显然，类似于之前做过的动态规划题，我们可以把状态f[i]定义为第1到i行最多能放多少个炮
兵。但在推导转移方程的时候，问题出现了。第i行哪些位置能放炮兵不仅仅由该行的地形决
定，由于每个炮兵还可以对上下各两行进行攻击，所以能放炮兵的位置还会由它上方的第一行
和第二行的状态来决定。所以一维DP不能解决这个问题，正确的答案应该是多维DP。在整个
转移的过程中，我们需要三行的摆放状态，第i行，第i－1行和第i－2行。而转移必定是由上
行的对应f值推到本行的对应f值，所以每一个f应该需要存储两行的信息，本行摆放状态和上
行摆放状态。这样我们可以定义一个三维的DP状态f[i][j][k]表示第i行摆放状态为j，第i－1行
摆放状态为k的时候，第1到i行最多能摆的炮兵数量。为了节省空间，其中的j和k都是在上一
步中我们计算出的zt数组的状态编号而不是具体的摆放状态值，在使用时，zt[j]和zt[k]才是实
际的状态。
那么如何转移呢，哪些情况才是可以转移的呢？按照一般动态规划的解题思路，本行某一
状态的答案必定是由上行某一状态的答案转移过来的。能够转移的两个状态事实上包含了三行
的炮兵摆放情况，而这三行的炮兵摆放情况只有全都不互相冲突才能顺利转移，否则会误伤。
与第一步中的做法类似，如果把这三行的炮兵摆放情况两两进行&运算，如果结果均为0，则
可以转移。讲到这儿，如果你足够细心，就会发现其实还漏考虑了一个条件，最开始我们讨论
的读入进来的数据到哪儿去了？如果转移的状态不符合题目对只能在平原摆放部队的要求怎么
办？在讲解读入的时候我有提到，用0表示平原，1表示山地来压缩状态来存储矩阵是有很大
好处的。请大家结合刚才讲到的做法，想想还需要满足什么条件才能转移？（请同学回答）没
错，把每一行的炮兵摆放情况再&一下那一行的压缩之后的地形状态，继续看是否为0就可以
了。这样转移方程也就不难理解了：f[i][j][k]=max{f[i-1][k][p]+__builtin_popcount(zt[j])}(
((zt[j] & zt[k])==0) && ((zt[k] & zt[p])==0) && ((zt[j] & zt[p])==0) && ( (zt[j] &
img[i]) == 0 ) && ( (zt[k] & img[i-1]) == 0 ) && ( (zt[p] & img[i-2]) == 0 ) )。其
中__builtin_popcount函数是系统自带的计算一个整数的二进制表示中有多少个1的函数，再
noip中是不允许使用的。来看一下代码。
for(int i=1;i<=n;i++){
for(int j=1;zt[j]<=ky[m];j++){
for(int k=1;zt[k]<=ky[m];k++){
int& fnow=f[i][j][k];
fnow=0;
int t;
for(int p=1;zt[p]<=ky[m];p++){
if( ((zt[j] & zt[k])==0) && ((zt[k] & zt[p])==0) && ((zt[j] & zt[p])==0) && (
(zt[j] & img[i]) == 0 ) && ( (zt[k] & img[i-1]) == 0 ) && ( (zt[p] & img[i-2]) == 0 )){
t=f[i-1][k][p]+__builtin_popcount(zt[j]);
fnow=max(fnow,t);
}
}
}
}
}
在代码中还用到了一个语言特性，注意到在定义fnow的时候，我在int后面加了一个&符号。
这代表此时定义的fnow并不是一个新的变量，而是f[i][j][k]的一个引用，也就是说我对fnow
的操作就相当于我对f[i][j][k]的操作。
至此，我们已经完成了这道题的大部分操作，下一步便是出答案的时候了。怎么找答案
呢？相对于之前复杂的思考，得到答案非常简单。我们只需要枚举j和k，找到f[n][j][k]的最大
值就可以了。
这道题我就讲到这里，如果有不懂的地方请大家赶紧提出。希望大家今天都能够把这道题
顺利地打出来。

by刘俊琦