这题我的思路是设 $f[i][s]$为第i行炮兵阵地状态为s时前i行总的最大炮兵阵地数

对于$i,s$枚举第$i-2$行的炮兵状态$s1$,第$i-1$行炮兵状态$s2$，第$i$行炮兵状态$s$，如果$s,s2,s1$不冲突

有$f[i][s]=max(f[i-2][s1]+count(s)+count(s2))$

$count$为统计二进制数中一的个数

#include<iostream>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
int f[110][1030];
int a[110][12];
int count(int s)
{
	int sum=0;
	while(s)
	{
		sum++;
		s=s&(s-1);
	}
	return sum;
}
int sc[10002];
int cun[190][2000];
int main()
{
	int N,M;
	cin>>N>>M;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			char ch;
			cin>>ch;
			if(ch=='P')
			{
				a[i][j]=1;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		int s=0;
		for(int j=1;j<=M;j++)
		{
			s=(s<<1);
			if(a[i][j]==1) s++;
		}
		sc[i]=s;//用sc来保存每行可放阵地的位置
	}
	for(int i=1;i<=N;i++)
	{
		int s=sc[i];
		for(int j=0;j<=(1<<M)-1;j++)
		{
			if(j&(j<<1))continue;
			if(j&(j<<2))continue;
			if(j&(j>>1))continue;
			if(j&(j>>2))continue;
			if((j&s)==j)
			{
				cun[i][0]++;
				cun[i][cun[i][0]]=j;
			}//提前处理每行的可行状态
		}
	}
	for(int j=1;j<=cun[1][0];j++)
	{
		int s=cun[1][j];
		f[1][s]=count(s);
	}
	for(int j=1;j<=cun[2][0];j++)
	{
		int s1=cun[2][j];
		for(int l=1;l<=cun[1][0];l++)
		{
			int s2=cun[1][l];
			if(s1&s2) continue;
			f[2][s1]=max(f[2][s1],f[1][s2]+count(s1));
		}
	}
	for(int i=3;i<=N;i++)
	{
		for(int j=1;j<=cun[i-2][0];j++)
		{
			int s1=cun[i-2][j];
			for(int k=1;k<=cun[i-1][0];k++)
			{
				int s2=cun[i-1][k];
				if(s1&s2)continue;
				for(int l=1;l<=cun[i][0];l++)
				{
					int s3=cun[i][l];
					if((s1&s3)||(s2&s3)) continue;
					f[i][s3]=max(f[i][s3],f[i-2][s1]+count(s2)+count(s3));//前i行总阵地数=前i-2行总数+i-1行阵地数+第i行阵地数
				}
			}
		}
	}
	int maxn=0;
	for(int i=1;i<=cun[N][0];i++)
	{
		maxn=max(f[N][cun[N][i]],maxn);
	}
	cout<<maxn;
	return 0;
}

我自己感觉思路没什么问题，不知道是不是测试数据太水，时间全都是500ms以内，但是WA了8个点