| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 26796 | Accepted: 10344 |
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 4phpPPPHHPPPPPHPPPHHPSample Output
6先发两个网上比较好的题解，再说下自己的理解
题解1:
由于是求的最多能放置的炮兵个数，就是求某一个状态下，它对应的炮兵个数最多，所以就想到dp方程肯定是那种dp[i+1]=max{dp[i-1]..}的形式，又考虑到每一行
的状态只和前两行有关系，所以考虑用dp来做，下面考虑如何用二进制位来表示一个状态及转移方程。
对于原始的矩阵，我们用1来表示可以放置炮兵，即对应图中的P，这样每一行都有一个可以放置炮兵的状态，存到rstate[N]中，用来check该行的状态是否合法。
由于当前行和前两行有关系，所以得用3维矩阵来保存一个状态下最多的炮兵个数，用dp[i][curst][PRest]表示当前第i行状态对curst，前一行状态为prest的最大炮兵数。
转移方程为dp[i][curst][prest]=max{dp[i-1][prest][preprest]}，这样求到最后一行之后，答案就是最后一行所有状态中最大的那个。程序初始化的时候需要对第一行
进行预处理，设置dp[0][st][0]=st合法&st中1的个数。这样进行下面的计算的时候，由于0状态肯定是和所有状态兼容的，所以就不会影响计算结果。
题解2：
思考方法：首先，一个炮的攻击有两行，所以对于第i行来讲，i-1行和i-2行对它有影响，i-3行及以上的都没有影响了，所以我们要得到第i行的信息，只需要知道i-1和i-2的信息（最近有个体会，DP要找到什么因素影响了当前你要求的东西，有影响的我们就处理，没影响的我们不用管）。接着我们就思考怎么表示状态。山用1表示，空地用0表示，空地放了兵也用1表示，那么对于一行，就是一个01的串，这是个二进制数，我们可以想到状态压缩压缩回来一个十进制数。
比如原地图01101011，那么0处可以放兵，所有那么多个0，可以变为1（但也要考虑炮与炮之间不能攻击），要枚举全部情况，我们很自然想到了dfs来枚举，很多解题报告是这样做的，这样确实也能解决，但不是最好的方法。最好的方法是位运算。
要想到位运算，要跳出思维的限制，在一行中，原有的1是固定不能变，炮不能放在山上。0是可以变为1的，但是要保证炮与炮之间不能攻击。要满足这两个要求，我们可以拆开来做。先满足了炮与炮不能互相攻击，然后在这些摆放中再选出跑不在山上的。
只考虑炮的话，枚举量2^10-1，但实际上满足的不足60个，网上有人问过60是怎么计算的，实际上准确的做法我也不确定，但是能大概推出来。一列最多10位，最多其实只能放4个炮，然后接着看3个炮，2个炮，1个炮，0个炮的情况，就可以大致算出。
枚举方法是 for(i=0; i<(i<<col); i++) if( !(i&(i<<1)) & !(i&(i<<2)) ) i是合法状态 这个是要点，要理解
int state[MAXM]; 保存状态（十进制数），是仅仅满足了炮与炮不互相攻击，但是没有满足炮不在山上
对于一开始的地图，还没放炮，它本身已经表示了一个状态，所以也先压成一个状态，保存在一个数组中
再者，我们得到了一个状态state[i]，我们怎么知道这个状态下放了多少炮啊？其实就是判断state[i]这个十进制数变为二进制数后有多少个1，这个要怎么统计呢？位运算！
并且把对应的士兵人数保存在 int soldier[MAXM]; //对应着，在state[i]状态下能放多少个士兵
int base[MAXR]; //第i行的原地图压缩成的一个状态
那么怎么判断炮不在山上呢？ 只要state[i] & base[r] = 0 ,就表示state[i]这个状态，可以放在r这行上，而且炮不会在山上，炮之间也不会攻击，这是个要点，理解
然后前面说了，i行，i-1行，i-2行的炮会互相影响，他们可能会互相攻击到对方，所以我们假设现在i行，i-1行，i-2行的炮的摆放情况分别是state[i],state[j],state[k]
只有当他们都不两两攻击的时候，这3个状态才能放在一起，否则这3个状态不能放在一起。那么怎么判断他们不会两两攻击呢，方法一样的
state[i] & state[j] = 0 state[i] & state[k] = 0 state[j] & state[k] = 0 ，三个要同时满足，要点，理解
你会发现多次需要用到 一种判断 a&b 是为0还是不为0，所以我们代码中将其写成宏定义方便查看，实际上写成宏后时间慢了一点
#define legal(a,b) (a&b) //判断两个状态共存时是否合法，合法为0，不合法为非0
最后看状态转移方程，设dp[r][i]表示第r行，状态为state[i]是的最大值，
dp[r][i]=max { dp[r-1][j]+dp[r-2][k] } + soldier[i]
也就是第r-1行的状态为state[j]，第r-2行的状态为state[k]的和，并加上当前行放了soldier[i]个士兵 ， 但要满足state[i],state[j],state[k]不能互相攻击
接着我们可以可以写成三维的形式 dp[r][i][j]= max{ dp[r-1][j][k]} + soldier[i] , dp[r][i][j]表示第r行状态为state[i]，第r-1行为state[j]的最大值
做题感悟：
之前做的两个状压DP都是选择的，即用了就不能再用了，所以就只是跳过标记的就行，而且一开始都是0，并没有像这题有地图限制，所以可以直接dfs，因为他不像这题有地形限制，所以像这类有地形限制的，比如标记一个点四周两个点都被标记，这样的，一般要初始化，先把所有可行的状态都找出来，这个题每一行，每个炮台左右两个格以内不能再有炮台，也就是每个1左右两边两个格子必须都是0，用位运算表示就是!(i&(i<<1)) && !(i&(i<<2))，把i的整体状态都左移1个跟两个，这样就可以看每个1左右两个空格有没有1了。。如果没有1，这说明就是一个可行的状态，就把他记录下来，这样每个炮台这一行的问题就解决了，直接枚举所有可行状态就行，那么这个炮台又只跟前面两行有关了，从第一行枚举过去，这个炮台下面的两个其实不用管，枚举过去就好了(类似反转问题），这个记录状态要学习一下。。。
由于当前行和前两行有关系，所以得用3维矩阵来保存一个状态下最多的炮兵个数，用dp[i][curst][prest]表示当前第i行状态对curst，前一行状态为prest的最大炮兵数。
转移方程为dp[i][curst][prest]=max{dp[i-1][prest][preprest]}，这样求到最后一行之后，答案就是最后一行所有状态中最大的那个。程序初始化的时候需要对第一行
前面的状态注意要跟分别跟前两行的地图比较下，这个题就差不多解出来了。
心得就是，像这种有特殊限制的，比如四周不能有等等，就提前初始化，把所有的情况都记录在一个数组，然后枚举情况就好了，其余的简单的，比如每一行只有一个，每一列只有一个，这样的完全可以直接dfs 比如这题：http://blog.csdn.net/QQ_34374664/article/details/54586529，还有状压dp其实“每一行的可行状态都是一样的”，枚举行的之后其实都是枚举相同的状态。。
我的代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define me(a) memset(a, 0, sizeof(a))using namespace std;int dp[115][70][70], maze[105], status[70], num[70], m, n, len;char str[111];int main(){ while(~scanf("%d%d", &n, &m)) { me(dp); me(num); me(maze); me(status); for(int i = 1; i <= n; i++) { scanf("%s", str); for(int j = 0; j < m; j++) { if(str[j] == 'H') { maze[i] += (1<<j); } } } len = 1; for(int i = 0;i < (1<<m); i++) { if(!(i&(i<<1)) && !(i&(i<<2))) { int k = i, sum = 0; while(k) { if(k&1) sum++; k >>= 1; } num[len] = sum; status[len++] = i; } } for(int i = 1; i < len; i++) { if(!(maze[1]&status[i])) { dp[1][i][1] = num[i]; } } for(int i = 2; i <= n; i++) { for(int j = 1; j < len; j++) { if(status[j]&maze[i]) continue; for(int k = 1; k < len; k++) { if(status[j] & status[k]) continue; if(status[k] & maze[i-1]) continue; for(int t = 1; t < len; t++) { if(status[t]&status[j]) continue; if(status[t]&status[k]) continue; if(status[t]&maze[i-2]) continue; dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t]+num[j]); } } } } int ans = 0; for(int i = 1;i < len; i++) for(int j = 1;j < len; j++) ans = max(ans, dp[n][i][j]); printf("%d/n", ans); } return 0;}一个比较详细的代码：
#include <cstdio>#include <iostream>#include <cstring>#define MAXR 110 //行数#define MAXC 15 //列数#define MAXM 70 //状态数#define max(a,b) a>b?a:b //返回较大值#define CL(a) memset(a,0,sizeof(a)) //初始化清空数组#define legal(a,b) a&b //判断两个状态共存时是否合法，合法为0，不合法为非0int 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];using namespace std;int main(){ CL(base); CL(state); CL(soldier); CL(dp); nums=0; scanf("%d%d",&row,&col); for(int i=0; i<row; i++) //先计算原始地图的状态数 { scanf("%s",g[i]); for(int j=0; j<col; j++) if(g[i][j]=='H') base[i]+=1<<j; //像0110000，这里计算为6 } for(int i=0; i<(1<<col); i++) //仅是两个炮兵不互相攻击的条件下计算所有状态 { if( legal(i,i<<1) || legal(i,i<<2)) continue; //i这个状态出现了士兵两两攻击 int k=i; while(k) //这个循环计算状态i的二进制形式里面有多少个1，也就是放了多少个士兵 { soldier[nums]+=k&1; //等价于k%2，相当于判断k的二进制形式里面有多少个1 k=k>>1; } state[nums++]=i; //保存这个合法的状态 } /***************************************/ //for(int i=0; i<nums; i++) printf("%d %d/n",state[i],soldier[i]); /***************************************/ for(int i=0; i<nums; i++) //先初始化dp[0][i][0]，即初始化第1行的情况 { if(legal(state[i],base[0])) continue; //在state[i]的基础上，还要满足士兵不能放在山上，这个判断就是处理这个问题的 dp[0][i][0]=soldier[i]; }// for(int i=0; i<nums; i++) //接着初始化dp[1][i][j]，即第2行的情况// {// if(legal(state[i],base[1])) continue;// for(int j=0; j<nums; j++) //枚举第1行的状态// {// if(legal(state[j],base[0])) continue;// if(legal(state[i],state[j])) continue;// dp[1][i][j]=max(dp[1][i][j] , dp[0][j][0]+soldier[i]);// //状态转移方程// }// } for(int r=1; r<row; r++) //第3行开始DP直到最后 for(int i=0; i<nums; i++) //枚举第r行的状态 { if(legal(state[i],base[r])) continue; for(int j=0; j<nums; j++) //枚举第r-1行的状态 { if(legal(state[j],base[r-1])) continue; if(legal(state[i],state[j])) continue; //第r行的士兵和第r-1行的士兵相互攻击 for(int k=0; k<nums; k++) //枚举第r-2行的状态 { if(legal(state[k],base[r-2])) continue; if(legal(state[j],state[k])) continue; //第r-1行的士兵和第r-2行的士兵相互攻击 if(legal(state[i],state[k])) continue; //第r行的士兵和第r-1 dp[r][i][j]=max(dp[r][i][j] , dp[r-1][j][k]+soldier[i]); } } } int ans=0; for(int i=0; i<nums; i++) for(int j=0; j<nums; j++) //枚举dp[row-1][i][j] ans=max(ans,dp[row-1][i][j]); printf("%d/n",ans); return 0;}
新闻热点
疑难解答
