司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），
也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；
一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
作为一个垃圾NOIP狗看见NOI题还是比较虚，又是状压dp，一开始完全是做都不敢做。
首先我们来分析这一道题的状态，由于这一步的转移牵扯到了上一步和上上一步，那么状态里至少会有两维表示上一步和上上一步。
题目最难的如何设计可转移的状态，上下各两格没有其他的士兵。看了题解才发现了一个非常精妙的操作，用一个2进数表示每个点有没有士兵，0表示有，1表示没有，那么这个数左移一位对这个数进行与操作的值不为0的话，则说明有一位左边一格是有兵的，同理左移两位对这个数进行与操作的值不为0的话，则说明有一位左边两格是有兵的，这样就处理出了在一条横线上的可行状态。对于一条竖线的话，直接进行与操作，有值则为不能放的。
在此还有一个问题就是如果快速判断是否是山丘。在处理的时候我们也将地形用2进制数表示，如果是山丘则为1。那么我们这时对于一个放兵的状态和这一行的地形进行与操作，那么如果有值则说明了这一位有兵在山丘上了，则不合法。
接着我们来考虑转移，根据之前分析的状态，我们可以用dp[i][sh][zhe]表示考虑到前i个，我们现在这个的状态是zhe，上一个状态为sh时的最大兵数。那么它便可以从合法的dp[i-1][ss][sh]表示考虑到前i-1个，我们现在这个的状态是sh，上一个状态为ss时的最大兵数转移而来。
最后答案就是所有考虑到最后一行里的可行解转移而来。
不过最后要注意一个细节，对于第一行，它是没有上一个状态的，所以需要将它的这一个状态直接初始化为这一行的兵数。
下附AC代码。
#include<iostream> #include<string.h> #define maxn 105 using namespace std; int n,m; int cnt; int g[maxn]; int state[maxn]; int sum[(1<<11)]; int dp[maxn][maxn][maxn]; int cal(int s) { int ans=0; for(int i=0;i<m;i++) { if(((s>>i)&1)) ans++; } return ans; } bool check(int s) { if((s&(s<<1))) return false; if((s&(s<<2))) return false; return true; } void findstate() { for(int i=0;i<(1<<m);i++) if(check(i)) { state[cnt++]=i; sum[i]=cal(i); } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { char a; cin>>a; if(a=='H') { g[i]|=(1<<j); } } } findstate(); memset(dp,-1,sizeof(dp)); for(int i=0;i<cnt;i++) if((g[0]&state[i])==0) { dp[0][0][i]=sum[state[i]]; } int ans=0; for(int i=1;i<n;i++) { for(int zhe=0;zhe<cnt;zhe++) { if(g[i]&state[zhe]) continue; for(int sh=0;sh<cnt;sh++) { if( (state[zhe]&state[sh] )|| (g[i-1]&state[sh]) ) continue; for(int ss=0;ss<cnt;ss++) { if(state[zhe]&state[ss]) continue; if(state[sh]&state[ss]) continue; if(state[ss]&g[i-2]) continue; if(dp[i-1][ss][sh]==-1) continue; dp[i][sh][zhe]=max(dp[i][sh][zhe],dp[i-1][ss][sh]+sum[state[zhe]]); } } } } for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++) { ans=max(ans,dp[n-1][i][j]); } cout<<ans<<endl; }