Belarus @ 2019-08-23 16:38:28
不管怎么样都输出0 不知道为什么 求助!!!
#include<bits/stdc++.h>
using namespace std;
const int maxn=110,maxm=12;
int n,m,a[maxn][maxm],f[3][(1<<maxm)-1][(1<<maxm)-1],ans;
set<int> s;
set<int>::iterator it;
set<int>::iterator it2;
inline int count(int x){
int cnt=0;
for(int i=m-1;i>=0;i--) if((x>>i)&1) cnt++;
return cnt;
}
inline bool valid(int row,int x){
if(s.find(x)==s.end()) return false;
for(int i=0;i<m;i++)
if(((x>>i)&1)&&(!a[row][i]))
return false;
return true;
}
int main(){
freopen("pbzd.in","r",stdin);
ios::sync_with_stdio(0);
memset(f,-0x3f,sizeof(f));
cin>>n>>m;
char c;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>c;
if(c=='P') a[i][j]=1;
else if(c=='H') a[i][j]=0;
}
s.insert(0);s.insert(1);
for(int i=0;i<=(1<<m)-1;i++)
if(((i&(i<<1))==0)&&((i&(i<<2))==0)&&((i&(i>>1))==0)&&((i&(i>>2))==0)){
s.insert(i);
f[0][i][0]=count(i);
}
f[0][0][0]=0;
for(it=s.begin();it!=s.end();it++){
int j=*it;
if(valid(1,j))
for(it2=s.begin();it2!=s.end();it++){
int k=*it2;
if(valid(0,k))
if(!(k&j))
f[1][j][k]=max(f[1][j][k],f[0][k][0]+count(j));
}
}
for(int i=1;i<n;i++)
for(int j=0;j<(1<<m);j++)
if(valid(i,j))
for(int k=0;k<(1<<m);k++)
if(valid(i-1,k) && k&j==0)
for(int l=0;l<(1<<m);l++)
if(j&l==0)
f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][k][l]+count(j));
for(it=s.begin();it!=s.end();it++)
for(it2=s.begin();it2!=s.end();it2++)
ans=max(ans,f[(n-1)%3][*it][*it2]);
cout<<ans;
return 0;
}