POJ 1185 炮兵阵地 （状压DP）

POJ 1185 炮兵阵地 （状压DP）

Description

Input

第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符(‘P’或者’H’)，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

Output

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

Sample Input

5 4PHPPPPHHPPPPPHPPPHHP

Sample Output

6

思路

好不容易看到的中文题，刚开始一直没有思路，总是想着每一个状态应该怎么存储，又应该怎么推导出以后的状态，无果。。。

首先从炮兵的攻击范围我们可以知道，第k行的炮兵放置与第k-1、k-2行有关。

我们把每一行的炮兵放置情况压缩成一个二进制数，即每一位代表当前位置是否有炮兵（1代表有，0代表没有）， ​​1011​​ 代表1、3、4位置有炮兵安置。

对于水平方向，如果 ​​i&i<<1 || i&i<<2​​ 为真的话，说明有两个炮兵之间的距离小于等于2，则不满足题意，对于其他情况，都不会出现问题，记录这些合法状态。

​​dp[i][j][k]​​​ 代表第 ​​i​​​ 行状态为 ​​state[j]​​​ ，第 ​​i-1​​​ 行状态为 ​​state[k]​​ 时的最优解。

我们用 ​​base[]​​​ 来存储每一行的地图，假如 ​​base[i]&state[0-nums]​​ 为真，即说明当前枚举的状态与地图冲突，无法放置。

状态转移方程： ​​dp[r][i][j]=max(dp[r][i][j], dp[r-1][j][k]+soldier[i])​​

最终结果： ​​max(dp[row-1][0-nums][0-nums])​​

AC 代码

#include #include#include #define MAXR 110 //行数#define MAXC 15 //列数#define MAXM 70 //状态数using namespace std;int row,col; //行列int nums; //仅是两个炮兵不互相攻击的条件下，符合条件的状态个数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; //保存合法的状态 } for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。