把一行空白可放的状态搜出来，放到一个数组里，然后空间就不会炸了，然后用位运算判断在转移的时候状态可不可行。
f[i][t][s]表示第i行为s，第i-1行为t的最大放置数量，然后从枚举k，max(f[i-1][k][t])+num[s]转移
i=1,i=2单独处理！
#include<cstdio> #include<cstring> #define maxn 101 #define maxm 11 int n,m,cnt,ans; int map[maxn],st[maxn],num[maxn]; int f[maxn][maxn][maxn]; char ch[maxn][maxm]; void dfs(int s,int step) { if(step>m) { st[++cnt]=s; for(int i=1;i<=m;i++) if(s&(1<<(i-1))) num[cnt]++; return; } if(step==1) dfs(s|(1<<(step-1)),step+1); else if(step==2) { if(s==0) dfs(s|(1<<(step-1)),step+1); } else if(!(s&(1<<(step-3))) && !(s&(1<<(step-2)))) dfs(s|(1<<(step-1)),step+1); dfs(s,step+1); } void prework() { memset(map,0,sizeof(map)); memset(st,0,sizeof(st)); memset(num,0,sizeof(num)); memset(f,0,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",ch[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(ch[i][j]=='H') map[i]|=(1<<(j-1)); cnt=0; dfs(0,1); } int max(int a,int b) { if(a>b) return a; else return b; } void mainwork() { ans=0; for(int i=1;i<=cnt;i++) if(!(map[1]&st[i])) { f[1][0][i]=num[i]; ans=max(ans,num[i]); } if(n>1) for(int i=1;i<=cnt;i++) if(!(map[2]&st[i])) for(int j=1;j<=cnt;j++) if(!(map[1]&st[j]) && !(st[i]&st[j])) f[2][j][i]=max(f[2][j][i],f[1][0][j]+num[i]), ans=max(f[2][j][i],ans); if(n>2) for(int i=3;i<=n;i++) for(int s=1;s<=cnt;s++) if(!(st[s]&map[i])) for(int t=1;t<=cnt;t++) if(!(st[t]&map[i-1])) for(int k=1;k<=cnt;k++) if(!(st[k]&map[i-2])) if(!(st[s]&st[t]) && !(st[s]&st[k]) && !(st[t]&st[k])) f[i][t][s]=max(f[i][t][s],f[i-1][k][t]+num[s]), ans=max(ans,f[i][t][s]); } void print() { printf("%d\n",ans); } int main() { while(~scanf("%d%d",&n,&m)) { prework(); mainwork(); print(); } return 0; }
