也算是比较基础的状压dp了，跟做过的第二道比较又稍微复杂了一点
需要记录之前两行的状态。。
统计结果也稍有不同
另外还学习了一个得到一个整数二进制位 1 的个数的位运算方法
详见代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; #define MAXN 10000 int s[70]; int num[70]; int cant[110]; int dp[110][70][70]; int ns; int n,m; int ct(int x) { int res=0; while(x) { res++; x&=(x-1); } return res; } void setstate() { memset(num,0,sizeof(num)); for(int i=0;i<1<<10;i++) { if((i&(i<<1))==0&&((i&(i<<2))==0)) { s[ns]=i; num[ns++]=ct(i); } } } void ini() { memset(cant,0,sizeof(cant)); char s[20]; for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<m;j++) { if(s[j]=='H') { cant[i]|=(1<<j); } } } } void solve() { memset(dp,0,sizeof(dp)); for(int i=0;i<ns&&s[i]<(1<<m);i++) { if((s[i]&cant[1])==0) dp[1][0][i]=num[i]; } for(int i=2;i<=n;i++) { for(int t=0;t<ns&&s[t]<(1<<m);t++) { if(s[t]&cant[i]) continue; for(int j=0;j<ns&&s[j]<(1<<m);j++) { if(s[j]&cant[i-2]) continue; for(int k=0;k<ns&&s[j]<(1<<m);k++) { if(s[k]&cant[i-1]) continue; if(s[j]&s[k]) continue; if(s[t]&cant[i]) continue; if((s[t]&s[j])||(s[t]&s[k])) continue; dp[i][k][t]=max(dp[i][k][t],dp[i-1][j][k]+num[t]); } } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<ns&&s[j]<(1<<m);j++) { for(int k=0;k<ns&&s[k]<(1<<m);k++) ans=max(ans,dp[i][j][k]); } } printf("%d ",ans); } int main() { ns=0; setstate(); while(scanf("%d%d",&n,&m)!=EOF) { ini(); solve(); } return 0; }