AcWing 292. 炮兵阵地
原题链接
中等
作者:
wangyj
,
2021-01-18 21:07:58
,
所有人可见
,
阅读 341
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,g[1010],f[2][1024][1024],cnt[1024];
vector<int>state;
bool check(int state)
{
for(int i=0;i<m;i++)if((state >> i & 1)&&((state >> i + 1 & 1)||(state >> i + 2 & 1)))return false;
return true;
}
int count(int state)
{
int res=0,i;
for(i=0;i<m;i++)if(state >> i & 1)res++;
return res;
}
int main()
{
int i,j,k,u,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=0;j<m;j++){
char c;
cin>>c;
g[i]+=(c=='H')<<j;
}
for(i=0;i<1<<m;i++)if(check(i))state.push_back(i),cnt[i]=count(i);
for(i=1;i<=n;i++)for(j=0;j<state.size();j++)for(k=0;k<state.size();k++)for(u=0;u<state.size();u++){
int a=state[j],b=state[k],c=state[u];
if(a&b|a&c|b&c)continue;
if(g[i]&b|g[i-1]&a)continue;
f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][u][j]+cnt[b]);
}
for(i=0;i<state.size();i++)for(j=0;j<state.size();j++)ans=max(ans,f[n&1][i][j]);
printf("%d\n",ans);
return 0;
}