司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。
当然本来有1024种情况，你筛一筛就只有60种
我们可以发现每一行都跟上两行有关，
这就很像scoi的扫雷
f[i][j][k]表示当前枚举到第i行，上一行的状态为j，上上行的状态为k
#include<bits/stdc++.h> #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } int n,m,now,sum[65],sta[65],SUM,f[105][65][65]; inline bool judge(int x) { if(((x<<1)&x)||((x<<2)&x))re 0; SUM=0; while(x) { if(x&1)++SUM; x>>=1; } re 1; } inline void pre() { char ss[20]; scanf("%s",ss+1); now=0; inc(j,1,m) now=now*2+(ss[j]=='P'); } int main() { rd(n),rd(m); int cnt=0; //预处理出二进制 inc(i,0,(1<<m)-1) if(judge(i)) { sta[++cnt]=i; sum[cnt]=SUM; } //初始化 pre(); inc(i,1,cnt) if((now|sta[i])==now) f[1][i][1]=sum[i]; inc(i,2,n)//这一行 { pre(); inc(kk,1,cnt) { if((now|sta[kk])!=now)continue; inc(j,1,cnt)//上一行状态 { if(sta[kk]&sta[j])continue; inc(k,1,cnt)//上上行状态 if(!(sta[kk]&sta[k])) f[i][kk][j]=max(f[i][kk][j],f[i-1][j][k]+sum[kk]); } } } int ans=0; inc(i,1,cnt) inc(j,1,cnt) ans=max(ans,f[n][i][j]); printf("%d",ans); re 0; }