状态压缩的动态规划

状态压缩的动态规划，实际上也是一种“暴力出奇迹”的做法。

一 模型

「SCOI2005」互不侵犯

在$N \times N$的棋盘里面放$K$个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$个格子。

$1 \le N \le 9, 0 \le K \le N^2$

1 暴力思路

先考虑暴力解法。
爆搜第一行的状态，在合法的情况下，再爆搜下一行状态，得到这两行的所有可行方案。然后递归向下一行求解。
直到得到前$N$行的可行方案，且当前方案放置了$K$个国王，此时累加答案。

2 从暴力到动态规划

一个国王攻击距离只有一个格子。这就是说，如果仅考虑前$i$行，那么当前求解第$i$行时，受其影响的只有第$i-1$行（下面的格子越界了不去考虑，左右的个子同在第$i$行，剩下的只在第$i-1$行）。

也就是说，第$i$行的状态可以由第$i-1$行转移过来。

然后我们灵稽一动，是不是设$f_{i,j}$表示考虑前$i$行放$j$个国王的解数，就能切了这题吗？
然而并不是。当前行和上一行之间，怎么保证满足限制且能快速的计算出满足限制的解数？

爆搜当前行和上一行的排列方案？
还是不行。存在后效性：当当前行的排列方案改变的时候，$f$的值也会发生变化，不能用$f_{i,j}$一个状态一概而过。

那么就得加一维状态，也就是把爆搜放到数组的维度里。

3 把爆搜变成数组的维度

不要听题目瞎扯。爆搜怎么可能变成数组的维度？！
实际上，是把排列方案变成数组的维度。这个排列方案也可称作“状态”，于是就有了“状态压缩的动态规划”。

我们考虑每一行，有$N$个位置，放置国王用$1$表示，不放国王用$0$表示，那么我们会得到一个01串，如下：
$$ 01101 $$
这是当$N=5$时的随机一行的一种状态。虽然它不合法，但是这没有关系。
它表示当前行，第一个位置没有国王，第二、三个位置有国王，第四个位置没有国王，第五个位置有国王。

那什么是“压缩”？
我们把上面的01串看作二进制。

$ (01101)2 = (13)10 $

所以我们把这个状态编号为$13$，这就是状态压缩。

有了状态压缩，我们就可以定义$f_{i,j,cur}$表示考虑前$i$行放$j$个国王，且放置状态为$cur$时的解数。
解决了后效性的问题。转移方程：
$ f_{i,j,cur}=1|i=1,j=sumbit(cur),j \leqslant K,exmslf(cur) $
$ f_{i,j,cur}=f_{i,j,cur}+f_{i-1,j-sumbit(cur),prv}|1<i \leqslant N,j \leqslant K,exmslf(cur,prv),exmcpl(cur,prv) $
其中，$cur$为当前行状态，$prv$为上一行状态，$sumbit$函数实现统一任意一个状态里国王放置的数量，$exmslf$函数实现检查任意一个状态是否合法（一行中是否有国王可以互相攻击），$exmcpl$函数实现检查任意两个状态是否可以相邻（上下两行是否有国王可以互相攻击）。

4 枚举状态

考虑怎么枚举状态。
当$N=5$时，状态最大为$(11111)_2$，最小为$(00000)_2$。
$(11111)_2=(100000)_2-(1)_2$
$ (100000)_2=1<<5=1<<N(=2^N) $
故状态在$0$到$1<<N$之间（不包括$1<<N$）。
（注：“$<<$”是位运算中的左移运算符）

所以只需要 for(int cur=0; cur<(1<<N); cur++) 就好了。

---

二 代码实现

1 sumbit函数

暴力分解二进制。

int sumbit(int s)
{
    int sum=0;
    while(s)
    {
        if(s&1) //如果二进制的最后一位是1
            sum++; //累加
        s>>=1;
    }
    return sum;
}

2 exmslf函数

原理：$a & b=1$表示$a,b$二进制上的某一位同时为$1$。

则当$cur$不满足单行要求时，$cur & (cur<<1)$与$cur & (cur>>1)$里面至少有一者运算结果为$1$。

bool exmslf(int s){
    return !(s&(s<<1)) && !(s&(s>>1));
}

3 exmcpl函数

原理同上。

bool exmcpl(int s1,int s2){
    return !(s1&s2) && !(s1&(s2<<1)) && !(s1&(s2>>1));
}

4 递推

for(int fst=0; fst<(1<<n); fst++)
    if(exmslf(fst) && sumbit(fst)<=k)
        f[1][sumbit(fst)][fst]=1;
    
for(int i=2;i<=n;i++)
    for(int cur=0; cur<(1<<n); cur++)
        for(int sum=sumbit(cur);sum<=k;sum++) 
            for(int prv=0; prv<(1<<n); prv++)
                if(exmslf(cur) && exmslf(prv) && exmcpl(cur,prv))
                    f[i][sum][cur]+=f[i-1][sum-sumbit(cur)][prv];

int ans=0;                
for(int lst=0; lst < (1<<n); lst++)
    if(exmslf(lst))
        ans+=f[n][k][ans];