n*m
P 和 M
P可以放人 M不行
人不能相互打到 问最多可以放多少人
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<map> using namespace std; #define MAXN 1<<10 char z[105][15]; int x[105]; int dp[105][200][200]; int num[200]; int cn[200]; int Count(int a) { int ans=0; while(a>0) { if(a&1) ans++; a=a>>1; } return ans; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",z[i]); memset(x,0,sizeof(x)); memset(dp,-1,sizeof(dp)); int cnt=0; int en=1<<m; for(int i=0;i<en;i++) if(((i&(i<<2))||(i&(i<<1)))==0) { cn[cnt]=Count(i); num[cnt++]=i; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) if(z[i][j]=='H') x[i]|=(1<<j); } for(int i=0;i<cnt;i++) { if(x[0]&num[i]) continue; dp[0][i][0]=cn[i]; } for(int i=1;i<n;i++) //行 { for(int j=0;j<cnt;j++) //这行的状态 { if(x[i]&num[j]) //不能矛盾 continue; for(int k=0;k<cnt;k++) //上一行的状态 { if(num[j]&num[k]) //相邻两行不能同时出现1 continue; for(int k1=0;k1<cnt;k1++) //上面第二行状态 { if(num[j]&num[k1]) //相邻两行不能同时出现1 continue; if(dp[i-1][k][k1]==-1) continue; dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][k1]+cn[j]); } } } } int ans=0; for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++) ans=max(dp[n-1][i][j],ans); printf("%d ",ans); } return 0; }