P2704 [NOI2001] 炮兵阵地

#include <iostream>
#include <cstring>
using namespace std;

int n,m,cnt[1<<12],num[1<<12],s[110][1<<12],f[110][110][110];
char c[110][12];

void init(){
	for(int i=0;i<(1<<m);i++){
		if(i&(i<<1)||i&(i<<2)||i&(i>>1)||i&(i>>2))continue;
		for(int j=1;j<=n;j++){
			int sum=0,flag=0;
			for(int k=0;k<m;k++){
				if(i&(1<<k)){
					if(c[j][m-k]=='H'){
						flag=1;
						break;
					}
					sum++;
				}
			}
			if(flag)continue;
			s[j][++cnt[j]]=i;
			num[i]=sum;
		}
	}
	return ;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	init();
/*	memset(f,-127,sizeof(f));
	for(int i=0;i<=(1<<11);i++){
		for(int j=0;j<=(j<<11);j++){
			f[0][i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[i];j++){
			cout<<num[s[i][j]]<<" ";
		}
		cout<<endl;
	}*/
	for(int i=1;i<=cnt[1];i++)	//处理第一排
			f[1][i][0]=num[s[1][i]];
	for(int i=1;i<=cnt[1];i++){	//第二排
		for(int j=1;j<=cnt[2];j++){
			if(!(s[1][i]&s[2][j])){ //判断是否冲突
				f[2][i][j]=num[s[1][i]]+num[s[2][j]];
			} 
		}
	}
	for(int i=3;i<=n;i++){//枚举行 
		for(int j=1;j<=cnt[i];j++){//枚举第i行状态 
			for(int k=1;k<=cnt[i-1];k++){//枚举第i-1行状态 
				if(!(s[i][j]&s[i-1][k]))
				for(int l=1;l<=cnt[i-2];l++){//枚举第i-2行状态
					if(!(s[i][j]&s[i-2][l])&&!(s[i-1][k]&s[i-2][l]))
					f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+num[s[i][j]]);
					//cout<<"i: "<<i<<"  j: "<<j<<"  k: "<<k<<"  l: "<<l<<" -> "<<f[i][j][k]<<endl;
				}
			}
		}
	}
/*	for(int i=1;i<=n;i++)
		cout<<cnt[i]<<" ";
	cout<<endl;*/
/*	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[i];j++){
			cout<<s[i][j]<<" ";
		}
		cout<<endl;
	}*/

	int ans=-1e9;
	for(int i=1;i<=cnt[n];i++){
		for(int j=1;j<=cnt[n-1];j++){
			ans=max(ans,f[n][i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}