状压DP - 简书

预备知识

位运算

常用的运算符共 6 种，分别为与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ << ）和右移（ >> ）

’&’符号，x&y，会将两个十进制数在二进制下进行与运算(都1为1，其余为0）然后返回其十进制下的值。例如3(11)&2(10)=2(10)。
’|’符号，x|y，会将两个十进制数在二进制下进行或运算（都0为0，其余为1）然后返回其十进制下的值。例如3(11)|2(10)=3(11)。
’ ^ ’符号，x^y，会将两个十进制数在二进制下进行异或运算（不同为1，其余为0）然后返回其十进制下的值。例如3(11)^2(10)=1(01)。
’ ~ ’符号， ~ x，按位取反。例如~101=010。
’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。
’>>’符号，是右移操作，x>>1，将x在二进制下的每一位向右移动两位，最左边用0填充，相当于给x/2，去掉x二进制下的最右一位。

常见的一些位运算

1.判断一个数字x二进制下第i位是不是等于1。

if( ( (1<<(i−1)) & x ) > 0 )

原理:1左移i - 1位成为 0000010000（其中i位第i位）通过与运算从而得知第i位是否为1

2.将一个数字x二进制下第i位更改成1。

x = ( 1<<( i - 1 ) | x

原理:1左移i - 1位成为 0000010000（其中i位第i位）通过或运算从而得知第i位是否为1

3.将一个数字x二进制下第i位更改成0。

x = x & ~(1 << ( i − 1 ) )

原理:通过对(1 << ( i − 1 ) )进行取反得到 1111101111(0 为第i位) 再进行与运算得到第i位为1的数字

4.把一个数字二进制下最靠右的第一个1去掉。

x = x & ( x− 1 )

原理:假设数字x为11111(2) 则x - 1 为 11110(2) 与运算则会把最后一位1去掉, 得到数字11110
若数字x为11100(2) 则x - 1为11011(2) 与运算得到 11000
很显然对于一串二进制数其最后一位可分为0/1两种情况,而一个数字可以分为两个前后部分: 不变的部分+变的部分
例如: x = 110111(2) 可分为: 110 111两部分 x - 1 则为 110 110
x = 110100(2) 可分为: 110 100两部分 x - 1 则为 110 011
后面变的部分通过与运算实现实现去掉靠右的第一个1

注:这里的分法并无什么要求, 110111(2) 分为 1101 11两部分也可. 所谓的分成两部分也只是为了便于理解为什么这样子可以去掉靠右的第一个1,有其他的理解方法亦可

这里只摘要了一些常见的位运算,感兴趣可自行查询其他运算

概述

状压DP是利用计算机二进制的性质来描述状态的一种DP方式。状压经常和BFS及DP连用。

使用二进制数枚举出每一种可能的状态,通过不同状态的转移从而得到最优解

可以看得出使用二进制数描述状态很容易让状态数成指数态势增长,时间复杂度很容易升高,优化可以通过条件优化不同状态之间的转移关系,从而降低复杂度

例题讲解:

骑士(P1896 [SCOI2005]互不侵犯)
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入格式
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式
所得的方案数

输入输出样例
输入 
3 2
输出 
16

解析:状压DP是利用计算机二进制的性质来描述状态的一种DP方式,在本题中用一串二进制数来描述一行的状态
例如在一个4行4列的格子中第二行的状态是1001 代表第二行的第一,第四个放了分别放了一个国王

我们怎么用DP的思维来思考这道题呢?
我们很清楚DP的特征是将一个大问题分解为若干个相似的子问题,并且问题的解决无后效性,也就是说这个子问题的决策之后不会再后续的问题决策产生影响,本题的特征是八个方向不能有1(1代表有国王) 我们可以通过每一行的方式来思考, 待解决的这一行的状态是由上一行的状态所决定的!
联系之前说的使用一串二进制数代表一行的状态,我们可以列出一行可以有多少种状态, 然后再找到多少对状态是可以上下堆叠的
举个例子:
我们前进的方向有四种:上下左右(这就是每一行的状态)
对于我们走的方向又有一定的规则:
向上走之后不能向下/右走(不同状态的堆叠)
这样子是不是很有些熟悉的感觉?和一道入门的DP很相似

image.png

题目链接:https://leetcode-cn.com/problems/unique-paths-ii/
机器人的方向只能向右/下只是走完其中一步之后还能继续走的方向是随机的(因为障碍物是随机的)
那么这题就很简单了

题中要求一个国王的八个方向都不能有另一个国王,则利用了上述的位运算分别是
x & (x << 1)左右方向无国王(求出一行具有的全部状态)
x & y 上下方向无国王 (判断上一行与这一行的上下方向)
x & (y<<1) 东南/东北方向无国王(判断上一行与这一行的东南/东北方向)
x & (y>>1) 西南.西北方向无国王(判断上一行与这一行的西南.西北方向)

下面给出状态方程:

dp[i][j][k] = dp[i - 1][t][k - total[j]]
i代表1 - i 行
j代表第几种状态
k代表使用了多少个国王
total代表每种状态放置了多少个国王
dp[i][j][k] 的含义就是 1 - i 行的棋盘, 其中第i行的状态为第j种状态,使用了k个国王的种数

完成本题需要以下要求

记录有多少种状态

vector<int> kinds;

记录每种状态含有多少个国王

vector<int> total;

3.dp

vector<vector<vector<long long> > >dp

记录状态并判断记录每种状态含有多少个国王--使用了预备知识的位运算

for (int i = 0; i < (1 << n); i++) {
        //cout << (i << 1)<<endl;
        if (i & (i << 1))//判断该二进制是否符合状态要求--是否左右含有国王
            continue;
        else {
            kind = 0;
            for (int j = 0; j < n; j++) {//该二进制数含有1的个数
                if (i & (1 << j))
                    kind++;
            }
            kinds.push_back(i);
            total.push_back(kind);
        }
    }

//init
//初始化第一行的状态
    for (int i = 0; i < kinds.size(); i++) {
        dp[1][i][total[i]] = 1;
    }
    //dp[0][1][0] = dp[0][1][0] = 1;
    for (int i = 2; i <= n; i++) {//行
        for (int j = 0; j < kinds.size(); j++) {//每行的可能状态
            for (int K = total[j]; K <= k; K++) {判断所求的k需要大于本行国王数目才能进行下列运算
                for (int t = 0; t < kinds.size(); t++) {//前一行的可能状态
                    if (!(kinds[j] & kinds[t]) && !(kinds[t] & kinds[j] << 1) && !(kinds[t] & kinds[j] >> 1))
                        dp[i][j][K] += dp[i - 1][t][K - total[j]];
                }
            }
        }
    }

优化思路:

可以建立不同状态之间的转移关系的状态图,来简化时间复杂度,例如第四个循环可以通过状态图优化不需要遍历所有状态

完整代码:


#include<iostream>
#include<vector>
using namespace std;
int n, k;
int main(void) {
    long long res = 0;
    int kind = 0;
    vector<int> kinds;
    vector<int> total;
    cin >> n >> k;
    //init
    for (int i = 0; i < (1 << n); i++) {
        //cout << (i << 1)<<endl;
        if (i & (i << 1))
            continue;
        else {
            kind = 0;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j))
                    kind++;
            }
            kinds.push_back(i);
            total.push_back(kind);
        }
    }
    //init var
    vector<long long> arr(k+1,0);
    vector<vector<long long> >temp(kinds.size(), arr);
    vector<vector<vector<long long> > > dp(n+1, temp);

    //dp
    //init dp
    for (int i = 0; i < kinds.size(); i++) {
        dp[1][i][total[i]] = 1;
    }
    //dp[0][1][0] = dp[0][1][0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < kinds.size(); j++) {
            for (int K = total[j]; K <= k; K++) {
                for (int t = 0; t < kinds.size(); t++) {
                    if (!(kinds[j] & kinds[t]) && !(kinds[t] & kinds[j] << 1) && !(kinds[t] & kinds[j] >> 1))
                        dp[i][j][K] += dp[i - 1][t][K - total[j]];
                }
            }
        }
    }
    for (int i = 0; i < kinds.size(); i++) {
        res += dp[n][i][k];
    }
    cout << res;
    return 0;
}