典型的状态压缩题，只是要定义dp[i][j][k]，
#include<bits/stdc++.h>
using namespace std;
int n,m,state[1<<10],tot=0;
int dp[110][66][66],sum[1<<10],mp[110];
int getsum(int x){
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
bool check(int x)
{
if(x&(x>>1)) return 0;
if(x&(x>>2)) return 0;
return 1;
}
int main(){
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=0;i<(1<<m);i++){
if(check(i))
{
state[++tot]=i;
sum[tot]=getsum(i);
}
}
for(int i=1;i<=n;i++) for(int j=0;j<m;j++)
{
char ch=getchar();
while(ch!='P' && ch!='H') ch=getchar();
if(ch=='H') mp[i]+=(1<<(m-1-j));
}
//处理第一行
for(int i=1;i<=tot;i++){
if(state[i]&mp[1]) continue;
dp[1][i][0]=sum[i];
}
//处理第二行
for(int i=1;i<=tot;i++){
if(mp[2]&state[i]) continue;
for(int j=1;j<=tot;j++){
if(mp[1]&state[j]) continue;
if(state[i]&state[j]) continue;
dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+sum[i]);
}
}
for(int i=3;i<=n;i++){
for(int k1=1;k1<=tot;k1++){
if(state[k1]&mp[i]) continue;
for(int k2=1;k2<=tot;k2++){
if(state[k2]&mp[i-1]) continue;
if(state[k2]&state[k1]) continue;
for(int k3=1;k3<=tot;k3++){
if(state[k3]&mp[i-2]) continue;
if(state[k3]&state[k2]) continue;
if(state[k3]&state[k1]) continue;
dp[i][k1][k2]=max(dp[i][k1][k2],dp[i-1][k2][k3]+sum[k1]);
}
}
}
}
int ans=0;
for(int i=1;i<=tot;i++){
for(int j=1;j<=tot;j++){
ans=max(ans,dp[n][i][j]);
}
}
printf("%d",ans);
return 0;
}
i指所在的行号，j指当前行的状态，k指上一行的状态