2X岁，是学生です

0%

状态压缩DP

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

指数级别的时间复杂度，因此数据范围稍大点的就不是状态压缩 $DP$。

状态压缩 $DP$ 有着一种解题的流程模式，一般是先预处理出各状态及其转移的合法性，再利用动态规划的一般方法求解。

蒙德里安的梦想

求把 $N \times M$ 的棋盘分割成若干个 $1 \times 2$ 的的长方形，有多少种方案。

例如当 $N=2$, $M=4$ 时，共有 $5$ 种方案。当$N=2$, $M=3$ 时，共有 $3$ 种方案。

alt

数据范围

$1 ≤ N, M ≤ 11$

思路：

首先为棋盘的每一列编号，为了便于状态的表示，编号从 $0$ 开始，一直编号到 $m$，即棋盘最后一列的下一列。（是一种技巧，之后说明）

$f[i][j]$ 的 $j$ 在本题中表示：在第 $i$ 列，由第 $i - 1$ 列的横置方块伸出部分在第 $i$ 列的覆盖情况的二进制表示，其中为 $0$ 的位表示当前列的上一列在该行没有伸出的方块覆盖当前列，为 $1$ 的位表示上一列该行的横置方块有伸出到当前列。

$f[i][j]$ 表示当第 $i$ 列的覆盖情况为 $j$ 时的合法摆放方案数。

什么是非法情况？

这道题比较难理解的是非法情况。

记第 $i - 1$ 列在第 $i$ 列的覆盖情况为 $j$，第 $i - 2$ 列在第 $i - 1$ 列的覆盖情况为 $k$。

而覆盖情况 $j$ 可以看作第 $i$ 列在第 $i - 1$ 列的覆盖情况，两者是相对的，因此我们利用 $j$ 和 $k$ 对第 $i-1$ 列进行非法情况检查。

非法情况分为两种：

  1. j & k != 0：非零即意味着第 $i$ 列和 $i - 2$ 列在第 $i - 1$ 列重复覆盖，这是非法的。

  2. j | k的结果中有连续奇数个零：要明确一点，$j$ 或者 $k$ 表示的都是横置方块的摆放情况，即每一个 $j$ 或者 $k$ 都代表着一种已经确定的方块横置情况，之后的方块只能竖直摆放。因此若第 $i - 1$ 列除去了横置方块的剩余位置有连续奇数个零，就意味着无法用 $1 \times 2$ 的方块竖放填满。

还有两个特殊情况需要考虑。

  1. 开始时的状态：由于第一列不可能有来自上一列的横置方块，因此 $f[0][0] = 1$，其余 $f[0][x]$ 均初始化为零。

  2. 结果的表示：之前所说的技巧就是这里。由于最终是填满棋盘，这个状态可以表示成 $f[m][0]$，即在棋盘的最后一列的下一列上，棋盘的最后一列没有横置方块的伸出覆盖。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N;
long long f[N][M];//有爆int可能
bool st[M];//状态预处理

int main()
{
    int n, m, cnt;
    scanf("%d%d", &n, &m);
    while(n || m)
    {
        //先预处理的意义：降低时间复杂度由11*2^11*2^11*11降到11*2^11*2^11
        for(int i = 0; i < 1 << n; ++i)
        {
            cnt = 0, st[i] = true;//统计连续的0的个数
            for(int j = 0; j < n; ++j)
            {
                if((i >> j) & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else ++cnt;
            }
            if(cnt & 1) st[i] = false;
        }
        memset(f, 0, sizeof(f));
        f[0][0] = 1;//i=0其实是第一列，对于第一列，只有前一列在此列伸出的方块数为0这一种放法
        for(int i = 1; i <= m; ++i)
            for(int j = 0; j < 1 << n; ++j)
                for(int k = 0; k < 1 << n; ++k)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        printf("%lld\n", f[m][0]);
        scanf("%d%d", &n, &m);
    }
    return 0;
}

最短Hamilton路径

给定一张 $n$ 个点的带权无向图，点从 $0$ 到 $n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 $Hamilton$ 路径。

$Hamilton$路径的定义：从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

数据范围

$1≤n≤20$

$0≤a[i,j]≤10^7$

思路：

按照最朴素、最暴力的做法，这道题应该有 $O(n!)$ 级别的时间复杂度。（那哪行啊！）

采用状态压缩 $DP$ 来优化。采用 $DP$ 来求解最值，表明并不对具体的路径顺序感兴趣，只对某一状态以及该状态从何处转移而来有兴趣。使用二进制数来表示某一节点是否已经经过，已经过置 $1$，还未经过置 $0$，$n$ 个节点只需使用 $n$ 位二进制数就可描述其经过状态。

时间复杂度从 $O(n!)$ 级别降低至 $O(n^2 \times 2^n)$。（至少还是个INT范围内的数）

$f[i][j]$ 中 $i$ 为记录各节点是否已经走过的二进制数，$j$ 表示当前所在的节点编号。

$f[i][j]$ 表示从 $0$ 走到 $j$，已经经过的节点二进制数记录为 $i$ (包括第 $j$ 个点)时的最短Hamilton路径长度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 21, M = 1 << N;
int myweight[N][N], f[M][N];

int main() 
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> myweight[i][j];
    memset(f, 0x3f, sizeof(f));
    //[i][j]表示从0走到j时，走过的点为i的二进制表示
    f[1][0] = 0;//i的状态表示到达了0点，经过的路径为只过了0这个点
    for (int i = 0; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1)//i的状态为0到j点的路径记录，因此第j位必须为1
            {
                int temp = i - (1 << j);
                for (int k = 0; k < n; ++k)//k表示到达点j的路径上到达j点前经过的最后一点
                    if ((temp >> k) & 1)
                        f[i][j] = min(f[i][j], f[temp][k] + myweight[k][j]);
            }
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}