【题目分析】 状压DP
【代码】
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int map[101],cnt=0,ans=0,n,m; char s[101]; int dp[101][70][70]; int rank[70]; int num[70]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) { scanf("%s",s+1); for (int j=1;j<=m;++j) map[i]|=((s[j]=='H')<<(m-j)); } for (int i=0;i<(1<<m);++i) if ((!((i<<1)&i))&(!((i<<2)&i))){ rank[++cnt]=i; for (int j=0;j<m;++j) if (i&(1<<j)) num[cnt]++; } for (int i=1;i<=n;++i) for (int j=1;j<=cnt;++j) for (int k=1;k<=cnt;++k) for (int l=1;l<=cnt;++l) if ((!(map[i]&rank[j]))&(!(rank[j]&rank[k]))&(!(rank[k]&rank[l]))&(!(rank[l]&rank[j]))) dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+num[j]); for (int i=1;i<=cnt;++i) for (int j=1;j<=cnt;++j) ans=max(ans,dp[n][i][j]); printf("%d\n",ans); }