代码
by liangbowen @ 2023-08-08 10:43:38
@[liangbowen](/user/367488) 哦哦好的，我还以为提交记录里可以看见代码
```cpp
#include<iostream>
using namespace std;
int n,m,ans,f[105][1024][1024];
string a[105];
bool s[105][1024];
bool check(int x){
int q1=0,q2=0;
while(x){
if((q1||q2)&&x&1)return 0;
q2=q1,q1=x&1;
x>>=1;
}
return 1;
}
int count(int x){
int sum=0;
while(x)sum+=x&1,x>>=1;
return sum;
}
bool valid(int i,int x){
int cnt=1;
if(!check(x))return 0;
while(x){
if(x&1){
if(a[i][m-cnt]=='H')return 0;
}
x>>=1,cnt++;
}
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n;i++)
for(int j=0;j<1<<m;j++)s[i][j]=valid(i,j);
for(int i=1;i<=n;i++){
for(int j=0;j<1<<m;j++){
if(!s[i][j])continue;
for(int k=0;k<1<<m;k++){
if(!s[i-1][k]||j&k)continue;
for(int l=0;l<1<<m;l++){
if((i>1&&!s[i-2][l])||j&l||k&l)continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+count(j));
}
}
}
}
for(int i=0;i<1<<m;i++){
if(!s[n][i])continue;
for(int j=0;j<1<<m;j++){
if(!s[n-1][j]||i&j)continue;
ans=max(ans,f[n][i][j]);
}
}
cout<<ans;
return 0;
}
```
by Austra @ 2023-08-08 10:51:21
```1<<m``` 似乎算太多次了
by Fesdrer_AK_IOI @ 2023-08-08 15:15:42
@[Austra](/user/124564) 刚刚出去玩了没看见（
你可以把所有有用的状态提前算出来，你这一部分中
```cpp
for(int k=0;k<1<<m;k++){
if(!s[i-1][k]||j&k)continue;
for(int l=0;l<1<<m;l++){
if((i>1&&!s[i-2][l])||j&l||k&l)continue;
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+count(j));
}
```
很显然有很多状态都会被 continue 掉，这是可以预处理的，这样你速度就会快非常多（这是这类型的状压 DP 常见技巧捏）
你可以看第二篇题解。
by liangbowen @ 2023-08-08 20:14:47
@[liangbowen](/user/367488) 谢谢解答，但我仍然没有搞懂，我已经预处理出所有不合法的情况将其continue了，我不知道还要怎样再预处理。
我看了一下第二篇题解。
```cpp
for(int i=3;i<=n;i++){
for(int j=1;j<=cnt;j++){ //当前一排状态
if((start[j]&F[i])==0){
for(int k1=1;k1<=cnt;k1++){ //上面第一排
if((start[j]&start[k1])==0&&(start[k1]&F[i-1])==0){
for(int k2=1;k2<=cnt;k2++){ //上面第二排
if((start[j]&start[k2])==0&&(start[k1]&start[k2])==0&&(start[k2]&F[i-2])==0){
//判断所有冲突情况
f[i][j][k1]=max(f[i][j][k1],f[i-1][k1][k2]+gs[j]);//从之前转移过来就行
}
}
}
}
}
}
}
```
他似乎也是一样的。
望解答，再次感谢您！
by Austra @ 2023-08-09 08:52:24
这我就不知道了，我跑得很快啊（）
by liangbowen @ 2023-08-09 18:17:52
https://www.luogu.com.cn/record/126944966
看一下我的
by 317_sky @ 2023-10-01 21:19:29
区别在循环的时候，题解里事先把合法情况预处理出来，循环次数比你少很多。
by 317_sky @ 2023-10-01 21:25:39