同样是状压dp，为什么我跑这么慢

Austra @ 2023-08-08 10:38:43

by liangbowen @ 2023-08-08 10:43:38

代码

by Austra @ 2023-08-08 10:51:21

@liangbowen 哦哦好的，我还以为提交记录里可以看见代码

#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 Fesdrer_AK_IOI @ 2023-08-08 15:15:42

1<<m 似乎算太多次了

by liangbowen @ 2023-08-08 20:14:47

@Austra 刚刚出去玩了没看见（

你可以把所有有用的状态提前算出来，你这一部分中

            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 Austra @ 2023-08-09 08:52:24

@liangbowen 谢谢解答，但我仍然没有搞懂，我已经预处理出所有不合法的情况将其continue了，我不知道还要怎样再预处理。

我看了一下第二篇题解。

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 liangbowen @ 2023-08-09 18:17:52

这我就不知道了，我跑得很快啊（）

by 317_sky @ 2023-10-01 21:19:29

https://www.luogu.com.cn/record/126944966 看一下我的

by 317_sky @ 2023-10-01 21:25:39

区别在循环的时候，题解里事先把合法情况预处理出来，循环次数比你少很多。