状压dp-1

· · 题解

基础的状压dp板子
本质上就是枚举每一行的合法选取方案并暴力判断
思路其他题解讲的很清楚，提供一个加详细注释的代码

#include<bits/stdc++.h>
#define mod 1000000000
using namespace std;
int a[20][20],all[20];
int right_[10010];
int f[20][10010];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            all[i]=(all[i]<<1)|a[i][j];//预处理出每一行的所有可放置地点，压缩成一个数 
    int maxx=1<<m;//每一位只有选或不选，那每一行最多有1<<m种方案 
    for(int i=0;i<maxx;++i)//枚举每一种状态,必须要从0开始,代表全部不选 
        right_[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);
        //如果没有(每一个点左边的点)和(每一个点右边的点)同时选中一个草地,那么状态合法 
    f[0][0]=1;
    for(int i=1;i<=n;++i)//枚举每一行情况 
        for(int j=0;j<maxx;++j)//枚举状态 
            if(right_[j]&&((j&all[i])==j))//这个状态合法,并且没有贫瘠的草地 
                for(int k=0;k<maxx;++k)//枚举上一行状态 
                    if((k&j)==0)//和上一行状态在同一列没有相同的草 
                        f[i][j]+=f[i-1][k],f[i][j]%=mod;//加上这种状态 
    long long ans=0;
    for(int i=0;i<maxx;++i)
        ans+=f[n][i],ans%=mod;//累加 
    printf("%lld",ans);
    return 0;
}