传送门
Analysis
简单的入门题，这个题解还不错 网上有人在问为什么状态数最多只有60多种 事实上，代码会告诉我们答案 运行一下，就知道了啊…… 能交给计算机的，为什么要自己想？？？
Code
#include<bits/stdc++.h>
using namespace std
;
int n
,m
;
char st
[15];
int base
[105],status
[1024];
int cnt
[1024],f
[105][70][70];
int num
=0;
int main(){
memset(f
,0,sizeof(f
));
scanf("%d%d",&n
,&m
);
int i
,j
,k
;
for(i
=0;i
<n
;++i
){
scanf("%s",st
);
for(j
=0;j
<m
;++j
)
if(st
[j
]=='H') base
[i
]+=(1<<j
);
}
for(i
=0;i
<(1<<m
);++i
){
if((i
&(i
<<1))||(i
&(i
<<2))) continue;
k
=i
;
while(k
){
cnt
[num
]+=(k
&1);
k
>>=1;
}
status
[num
++]=i
;
}
for(i
=0;i
<num
;++i
){
if(status
[i
]&base
[0]) continue;
f
[0][i
][0]=cnt
[i
];
}
for(i
=1;i
<n
;++i
){
for(j
=0;j
<num
;++j
){
if(status
[j
]&base
[i
]) continue;
for(int k
=0;k
<num
;++k
){
if(status
[k
]&base
[i
-1]) continue;
if(status
[k
]&status
[j
]) continue;
for(int p
=0;p
<num
;++p
){
if(status
[p
]&base
[i
-2]) continue;
if(status
[p
]&status
[k
]) continue;
if(status
[p
]&status
[j
]) continue;
f
[i
][j
][k
]=max(f
[i
][j
][k
],f
[i
-1][k
][p
]+cnt
[j
]);
}
}
}
}
int ans
=-1;
for(i
=0;i
<num
;++i
){
for(j
=0;j
<num
;++j
)
ans
=max(ans
,f
[n
-1][i
][j
]);
}
cout
<<ans
;
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-5028544.html
