P2704，20pts，悬关求调

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int n,m,can[105],lst[(1<<10)+7],f[3][66][66],cnt=0,popcnt[(1<<10)+7],ans=-1;
bool check1(int i,int j){
	if(((i&(j<<1))==0)&&((i&(j<<2))==0)) return 1;
	else return 0;
}
int pcnt(int x){
	int cnt=0;
	while(x>0){
		cnt++;
		x=x&(x-1);
	}
	return cnt;
}
signed main(){   
	string str;        
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>str;
		for(int j=0;j<m;j++){
			if(str[j]=='H'){
				can[i]<<=1;
				can[i]|=1;
			}
		}
	}
	for(int i=0;i<(1<<m);i++){
		if(check1(i,i)){		
			lst[++cnt]=i;
			popcnt[cnt]=pcnt(i);			
		}
	}
	for(int i=1;i<=cnt;i++){
		if(can[1]&lst[i]) continue;
		f[1][0][i]=popcnt[i]; 
	}
	for(int i=1;i<=cnt;i++){
		if(can[2]&lst[i]) continue;
		for(int j=1;j<=cnt;j++){
			if(can[1]&lst[j]||lst[i]&lst[j]) continue;
			f[2][j][i]=popcnt[i]+popcnt[j]; 
		}
	}
	for(int i=3;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			if(can[i]&lst[j]) continue;
			for(int k=1;k<=cnt;k++){
			if(can[i-1]&lst[k]||lst[k]&lst[j]) continue;
				for(int z=1;z<=cnt;z++){
					if(can[i-2]&lst[z]||lst[z]&lst[j]||lst[k]&lst[z]) continue;
					f[i%3][k][j]=max(f[i%3][k][j],f[(i-1)%3][z][k]+popcnt[j]);
					ans=max(ans,f[i%3][k][j]);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}