传送门
状压dp经典题。
我们把每一行的状态压成01串。
预处理出每一行可能出现的状态，然后转移每个被压缩的状态的1的个数就行了。
注意当前行转移要考虑前两行的状态。
还要注意只有一行的情况。
代码：
#include<iostream>
#include<cctype>
#include<cstdio>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int sta[105][70],tot[105],n,m,f[105][70][70],cal[105][70];
inline int calc(int x){
int ret=0;
while(x)x-=x&-x,++ret;
return ret;
}
int main(){
n=read(),m=read(),tot[0]=1;
for(int i=1;i<=n;++i){
char s[15];
int x=0;
scanf("%s",s);
for(int j=0;j<m;++j)if(s[j]=='H')x|=1<<j;
for(int j=0;j<(1<<m);++j){
if((j&(j<<1))||(j&(j<<2))||(j&x))continue;
sta[i][++tot[i]]=j,cal[i][tot[i]]=calc(j);
}
}
for(int i=1;i<=tot[1];++i)f[1][i][1]=cal[1][i];
for(int i=1;i<=tot[2];++i)
for(int j=1;j<=tot[1];++j){
if(sta[2][i]&sta[1][j])continue;
f[2][i][j]=max(f[2][i][j],f[1][j][1]+cal[2][i]);
}
for(int i=3;i<=n;++i){
for(int j=1;j<=tot[i];++j)
for(int k=1;k<=tot[i-1];++k){
if(sta[i][j]&sta[i-1][k])continue;
for(int l=1;l<=tot[i-2];++l){
if((sta[i][j]&sta[i-2][l])||(sta[i-1][k]&sta[i-2][l]))continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+cal[i][j]);
}
}
}
int ans=0;
for(int i=1;i<=tot[n];++i)
for(int j=1;j<=tot[n-1];++j){
if(sta[n][i]&sta[n-1][j])continue;
ans=max(ans,f[n][i][j]);
}
cout<<ans;
return 0;
}