棋盘图状态压缩问题常出现条件

①在棋盘中有几个点不能放置物品

我们只用将初始的这个状态存下来，然后在最后状态转移的时候判断一下即可

for(int i=1;i<=n;i++)//这是存初始状态的最简代码
    {
        int cn=0;
        for(int j=0;j<m;j++)//正序倒序都无所谓，不影响题目
        {
            char x;
            cin>>x;
            if(x=='H') s[i]+=1<<j; 
        }
    }

②控制棋盘中放置物体的数量最多为k

这种情况我们需要再开一维数组和再加一层循环然后将每一个状态的布置数量存放在一个数组中

//存数组
int count(int x)
{
    int res=0;
    for(int i=0;i<m;i++) if(x>>i&1) res++;
    return res;
}
for(int i=0;i<1<<m;i++)
    {
        if(check(i)) ve.push_back(i),cnt[i]=count(i);
    }

我们只用将初始的这个状态存下来，然后在最后状态转移的时候判断一下即可

$$%quad$$

棋盘图状态压缩问题常用表示答案方法

一般求答案都是输出dp[n][x],所有符合的x相加，但是我们可以再多加几层，用其他的状态一次性表示出题目要求的状态

$$%quad$$

优化

1.要是当前状态只与前一维状态有关联，可以利用滚动数组来转移

2.能到达当前状态的所有状态最好先预处理出来，这样速度会快