本文共 1462 字，大约阅读时间需要 4 分钟。

状压dp

状态压缩+dp。把某一个需要用0和1来表示的图看成二进制，然后转成10进制，从而把本来需要一个数组来表示的转态转换为一个数来表示。并且通过位运算优化计算速度，和dp结合起来就是状压dp。我自己的理解，应该是这样子。之前看过一篇数独的题解，那时只知道代码里全是二进制来存储情况，现在想想那好像就是状压dp了吧。

POJ 1185 炮兵阵地

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由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

感觉难点就在状态转移方程上，dp[i][j][k]表示第i行在士兵排列状态为j的情况且i-1行士兵排列状态为k的情况下的最大的士兵数量。

因为每个士兵射程为2，所以这里只需要第i行和第i-1行来标识dp的状态。 首先要先初始化第1行所有种士兵排列且前一行没有士兵(因为是第一行)情况下的dp 之后从第二行到最后一行，先满足此行士兵不在山上，后再满足上一行士兵不在山上且士兵不相互攻击，再满足上上行士兵不在山上且都不相互攻击下，dp的最大值。 最后遍历最后一行找出最大的ans就可以了。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxr=105, maxc=15, maxm=80;int row, col;int base[maxr];	//第i行压缩成一个状态 int state[maxm];	//两个炮兵互不攻击条件下，符合条件的状态 int soldier[maxm];	//state[i]状态下能放多少炮兵 int dp[maxr][maxm][maxm];	//dp[i][j][k] 表示第i行状态为state[j]，第i-1行状态为state[k]时的最优解char g[maxr][maxc];	int main(){   	scanf("%d%d", &row, &col);	for (int i=0; i
       
        >=1;		}	 		state[nums++]=i;	} 		//初始化dp[0][i][0](第一行)在士兵排列状态为i的情况 	for (int i=0; i