Stars_never_set @ 2023-01-18 17:01:55
初学状压，自己想了想有思路但是只过了第一个点，大佬救救我。
$ mp_i $ 存第 $ i $ 的地图，0 表示平原，1表示山地。
$ g_i $ 存符合炮兵攻击范围的队形。
$ cnt_i $ 表示 $ i $ 的二进制的炮兵数量。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<10);
const int IM=2147483647;
const long long LLM=9223372036854775807;
inline int read()
{
int x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') y=-y;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
return x*y;
}
int n,m,num,g[N],mp[N],cnt[N],f[3][N][N];
string s;
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)//初始化存地形
{
cin>>s;
for(int j=0;j<m;j++)
{
mp[i]<<=1;
if(s[j]=='H') mp[i]++;
}
}
for(int i=0;i<(1<<n);i++)
{
int p=i;
while(p){if(p&1) cnt[i]++;p>>=1;}
if((!(i&(i<<2)))&&(!(i&(i>>2)))&&(!(i&(i<<1)))&&(!(i&(i>>1)))) g[++num]=i;//存炮兵可能队形
}
for(int i=1+1;i<=n+1;i++)//从第二行开始循环
{
for(int l=1;l<=num;l++)
{
int s1=g[l];
if(s1&mp[i]) continue;//判断s1在第i行是否可行
for(int r=1;r<=num;r++)
{
int s2=g[r];
if((s2&mp[i-1])||(s1&s2)) continue;//判断s2在第i-1行是否可行 以及s1和s2是否冲突
for(int k=1;k<=num;k++)
{
int s3=g[k];
if((s3&mp[i-2])||(s1&s3)||(s2&s3)) continue;//同上
f[i%3][s1][s2]=max(f[i%3][s1][s2],f[(i-1)%3][s2][s3]+cnt[s1]);//转移
}
}
}
}
int ans=0;
for(int i=1;i<=num;i++)
{
int s1=g[i];
for(int j=1;j<=num;j++)
{
int s2=g[j];
if(s1&s2) continue;
ans=max(ans,f[n%3][s1][s2]);
}
}
printf("%d\n",ans);
return 0;
}
```