题目大意：定义一个炮兵会影响该点所在坐标上下左右两个格子的范围，求一个 N*M 的网格里最多可以放多少个炮兵。

题解：发现这个问题有需要记录两个状态，即：上一层的状态和上两层的状态，若直接进行记录，空间可能会起飞。发现对于一个合法的状态来说，需要满足一行中相邻的两个 1 必须位距离大于等于 2，且满足山地位置不能放炮兵，仅考虑第一个约束条件，先打一个表发现，在 1024 个状态范围内仅有 60 个状态满足第一个条件，因此采用直接记录下满足约束 1 的状态，并通过记录每一行的山地平原情况进行位与即可得到合法状态。时间复杂度为 \(O(100*60*60*60)=O(Accepted)\)。

代码如下

#include <bits/stdc++.h>

using namespace std;

char s[20];

int n,m,ans;

int G[101],f[101][61][61],valid[61],tot,num[61];

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%s",s+1);

		for(int j=1;j<=m;j++)if(s[j]=='H')G[i]|=1<<j-1;

	}

	for(int i=0;i<1<<m;i++)

		if(!(i&i<<1)&&!(i&i<<2)){

			valid[++tot]=i;

			int res=i;

			while(res)res-=res&-res,++num[tot];

		}

}

void solve(){

	for(int i=1;i<=tot;i++)

		for(int j=1;j<=tot;j++)

			if(!(valid[i]&valid[j])&&!(valid[i]&G[2])&&!(valid[j]&G[1]))

				f[2][i][j]=num[i]+num[j];

	for(int i=3;i<=n;i++)

		for(int j=1;j<=tot;j++)if(!(valid[j]&G[i]))

			for(int k=1;k<=tot;k++)

				if(!(valid[k]&G[i-1])&&!(valid[k]&valid[j]))

					for(int w=1;w<=tot;w++)

						if(!(valid[w]&G[i-2])&&!(valid[w]&valid[k])&&!(valid[w]&valid[j])){

							f[i][j][k]=max(f[i][j][k],f[i-1][k][w]+num[j]);

							ans=max(ans,f[i][j][k]);

						}

	printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}