司令部的将军们打算在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
还是找不好状态转移方程，其余都写对了，方程又错。 QAQ 。。。
分析 ： 因为是和前两行的状态有关，所以要用三维数组来存储状态。
这里DP[i][j][k]表示 第 i 行的状态为 k 且 i-1 行的状态为 j 的时候 能够存储的最大人数
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long longconst int N = 12;
const int MAX = 1000;int state[MAX],sz;
int cnt[100];
void init(int m){memset(cnt,0,sizeof(cnt)); // 每个状态有几个1 memset(state,0,sizeof(state));// 存储 每一行不会攻击的状态for(int i=0;i<(1<<m);i++){if(i&(i<<1)) continue;int pos=-1,flag=1; int ge=0;for(int j=0;j<m;j++){if((i>>j)&1){ge++;if(pos==-1) pos=j;else {if(j-pos<=2) {flag=0;}else pos=j;}}}if(!flag) continue;cnt[sz]=ge; state[sz++]=i;}
}LL cur[110],dp[110][100][100];
void InPut(int n,int m){for(int i=1;i<=n;i++){cur[i]=0; char s[15];scanf("%s",s);int a;for(int j=0;s[j];j++){if(s[j]=='P') a=0;else if(s[j]=='H') a=1;cur[i]=(cur[i]*2+a); // 将二进制取反，然后状压为一个整数}}
}void solve(int n){memset(dp,-1,sizeof(dp));for(int i=0;i<sz;i++) {if(cur[1]&state[i]) continue;dp[1][0][i]=cnt[i];}for(int i=2;i<=n;i++){for(int a=0;a<sz;a++){if(cur[i]&state[a]) continue;for(int b=0;b<sz;b++){if(state[b]&state[a]) continue;for(int c=0;c<sz;c++){if(state[a]&state[c]) continue;if(dp[i-1][c][b]!=-1)// 排除掉 i-1行的无效状态dp[i][b][a]=max(dp[i][b][a],dp[i-1][c][b]+cnt[a]);}}}}LL ans=0;for(int i=0;i<sz;i++){for(int j=0;j<sz;j++){ans=max(ans,dp[n][i][j]);}}printf("%lld\n",ans);
}int main(){int n,m;while(~scanf("%d",&n)){scanf("%d",&m);init(m);InPut(n,m);// for(int i=1;i<=n;i++) printf("%d ",cur[i]);solve(n);}
return 0;
}