fishmenomelon @ 2022-10-07 10:24:44
样例本地输出 6
,你谷在线ide输出 7
#include<cstdio>
#include<algorithm>
int f[105][205][205],a[105];
int state[205],size[205],cnt;
char mp[105][15];
int n,m,U;
void pre(){
U=(1<<m)-1;
state[0]=0;size[0]=0;
for(int S=1;S<=U;++S){
if((S&(S<<1))||(S&(S>>1))||(S&(S<<2))||(S&(S>>2)))continue;
state[++cnt]=S;
size[cnt]=__builtin_popcount(S);
}
for(int S=0;S<=cnt;++S)
if(!(state[S]&a[1]))
f[1][S][0]=size[S];
for(int S=0;S<=cnt;++S)
for(int T=0;T<=cnt;++T)
if((!(state[S]&a[1]))&&(!(state[T]&a[2]))&&(!(state[S]&state[T])))
f[2][T][S]=size[S]+size[T];
}
int main(){
scanf("%d%d",&n,&m);getchar();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)mp[i][j]=getchar();
getchar();
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[i]=(a[i]<<1)+(mp[i][j]=='H');
pre();
for(int i=3;i<=n;++i)
for(int S=1;S<=cnt;++S)if((!(a[i]&state[S])))
for(int T=1;T<=cnt;++T)if((!(a[i-1]&state[T]))&&(!(state[S]&state[T])))
for(int V=1;V<=cnt;++V)if((!(a[i-2]&state[V]))&&(!(state[S]&state[V]))&&(!(state[T]&state[V])))
f[i][S][T]=std::max(f[i][S][T],f[i-1][T][V]+size[S]);
int ans=0;
for(int S=0;S<=cnt;++S)
for(int T=0;T<=cnt;++T)
ans=std::max(ans,f[n][S][T]);
printf("%d\n",ans);
return 0;
}
by fishmenomelon @ 2022-10-07 10:39:59
已将scanf
改成cin
,90pts