https://loj.ac/problem/10173
题目描述
一个\(N\times M\)的网格，每个炮兵可以攻击到从它的位置上下左右\(2\)格以内远的位置，有一些位置不能放置炮兵，求部署时炮兵两两间不攻击的方案数。
思路
我们先无视该位置能否放炮兵，先预处理处如果这一行都能放炮兵时的状态，接下来考虑由于炮兵会影响到两行，暴力记录空间难以开下，所以我们省去堆当前这一行状态的保存，直接记\(f[i][S1][S2]\)表示第\(i\)行时\(i-1\)行为\(S1\)，\(i-2\)行为\(S2\)时的答案数，那么我们直接枚举当前行，前两行的状态进行转移即可。
代码
#include<bits/stdc++.h>
using namespace std;
int a[110];
int sum[66],f[110][66][66],p[66];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int s=0;
for(int j=1;j<=m;j++)
{
char ch=getchar();
while(ch!='P'&&ch!='H')ch=getchar();
s=s*2+(ch=='H');
}
a[i]=s;
}
int cnt=0;
for(int i=0;i<(1<<m);i++)
{
if((i&(i<<1))||(i&(i<<2)))continue ;
int k=0;
for(int j=0;j<m;j++)if(i&(1<<j))++k;
p[++cnt]=i;
sum[cnt]=k;
}
for(int i=1;i<=cnt;i++)
if(!(p[i]&a[1]))f[1][i][0]=sum[i];
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
if(!(p[i]&p[j])&&!(p[i]&a[2]))f[2][i][j]=f[1][j][0]+sum[i];
for(int i=3;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
{
if(p[j]&a[i])continue ;
for(int l=1;l<=cnt;l++)
{
if(p[j]&p[l])continue ;
for(int r=1;r<=cnt;r++)
if(!(p[j]&p[r]))f[i][j][l]=max(f[i][j][l],f[i-1][l][r]+sum[j]);
}
}
}
int ans=0;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
ans=max(ans,f[n][i][j]);
printf("%d",ans);
}