[学习笔记]状态压缩动态规划

Andrewzdm · 2020-06-07 18:29:03 · 个人记录

简介

状态压缩类动态规划（简称状压DP）也是一种很特殊的 DP 算法，其精髓就是将所有物品的状态（一般是选或不选，用01表示，当然也有特殊情况）压缩成一个整数，进行状态的转移并节约空间。

使用情境

使用情境还是很明显的，有以下特征：

每个物品的可能状态数比较少，比如要么选要么不选，就两种可能；
数据范围的某一个维度非常小，一般在 20 以内（这个提示可以说是很明显了，要么搜索要么状压）

时间复杂度

状压 DP 的时间复杂度一般都为指数级，即不能在多项式内的时间复杂度解决，这也就是为什么数据范围的某一个维度会很小。

关于状态

状压 DP 的状态的数组下标可以分为两类：一类是直接用状态压缩成的整数表示，这一类的题目的状态基本都是有效的；另一类是先筛选出有效状态并存储，然后用数组下标 i 表示“第 i 个有效状态”，这一类题目会因为一些限制条件导致有效状态的数目比总可能状态的数目要少很多。

有效状态的筛选

对于压缩成二进制数的题目，我们可以枚举所有的状态，然后进行判断，符合条件的就存储下来。比如这是某一道状压 DP 题目的代码片段：

for (int i = 0; i < (1 << n); i++)  //枚举
        if ((i & (i << 1)) == 0)  //判断
        {
            cnt++;
            a[cnt] = i;
            b[cnt] = get(i);
        }

对于一些特殊题目，压缩成的数不是二进制，我们可以通过 DFS 筛选出有效状态，比如下面这样：（这道题是一本通 5.4 练习 1 涂抹果酱），用 string 存储压缩的三进制数）

void dfs(int x, char last)
{
    if(x > m)
    {
        a[++cnt] = tmp;
        if(tmp == spe)
            idx = cnt;
        return;
    }
    for(char i = '1'; i <= '3'; i++)
    {
        if(i == last)
            continue;
        tmp += i;
        dfs(x + 1, i);
        tmp.erase(x - 1, 1);
    }
    return;
}

前面也提到过，我们还可以通过记忆化搜索的方式实现状压 DP，这样的话无效状态是不会被搜到的，不用筛选有效状态。我就不举栗子了。

压缩成二进制数是最常见的情况，这就要求我们会基本的位运算。

一些特殊的位运算操作

Note：以下默认二进制整数的最低位为第 0 位。

将 x 的二进制表示中第 i 位变成 1：x |= (1 << i);；
查询 x 的二进制表示中第 i 位是否为 1：(x & (1 << i)) > 0，或 ((x >> i) & 1) > 0，是则返回 true，否则返回 false；
将 x(x > 0) 的二进制表示中最后一位 1 变成 0：x &= (x - 1)；
返回 x 的二进制表示中最后一位 1 所对应的 2^k 值（即我们熟知的 \operatorname{lowbit}）：x & (-x)；
已知状态 S' 是状态 S 的子集，得到 \complement_S S'：S ^ SS；

枚举状态 S 的子集 S'：

for(int SS = S; SS; SS = (SS - 1) & S)

若要枚举真子集，改为如下代码即可：

for(int SS = (S - 1) & S; SS; SS = (SS - 1) & S)

为了统计 x 的二进制表示中 1 的个数，我们可以写出这样一个比较高大上的操作，时间复杂度即为 x 的二进制表示中 1 的个数，最坏为 O(\log x)。

int get(int x)
{
    int res = 0;
    while(x > 0)
    {
        res++;
        x &= x - 1;
    }
    return res;
}

例题1

NOIP2016提高组愤怒的小鸟

看到“至少发射多少只小鸟”，又发现不能用贪心（反正我是没想到），于是想到 DP。

看到 n \le 18，就知道要用状压了。

首先要想到很关键的一步：题目给定的抛物线用两点就能确定。

于是自然而然地想到了思路：

设计状态：我们可以把每一只猪有没有被击落表示为 0 和 1，击落了就是 1，反之就是 0。由于题目对猪的击落顺序没有限制条件，所以不存在无效状态，我们直接把状态写进数组下标。
设计转移：每次枚举两只猪，将它们击落（尽管可能有猪已经被击落过了，但我们的这只小鸟就朝着这两只猪的方向发射），将原状态的这两位变成 1 形成新状态，显然要用 push 型转移。而我们在击落两只猪的同时确定了一条抛物线，我们可以算出这条抛物线的解析式，并且康康它能不能顺便击落其它的猪。

接下来就是代码时间：

#include<iostream>
#include<algorithm>
#include<cmath>
#define EPS 1e-6
using namespace std;
int n, m;
const int maxn = 20;
double x[maxn], y[maxn];
int line[maxn][maxn], dp[1 << maxn];

void solve(int i, int j)  //算出解析式
{
    double x1 = x[i], x2 = x[j], y1 = y[i], y2 = y[j], a, b;
    b = (x1 * x1 * y2 - x2 * x2 * y1) / (x1 * x1 * x2 - x2 * x2 * x1);
    a = (y1 - x1 * b) / (x1 * x1);
    if(a >= 0)
        return;
    for(int k = 1; k <= n; k++)
        if(fabs(a * x[k] * x[k] + b * x[k] - y[k]) <= EPS)
            line[i][j] |= (1 << (k - 1));
    //line[i][j]表示这条抛物线能击落哪些猪
    return;
}

void work()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            line[i][j] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            solve(i, j);
    fill(dp, dp + (1 << n), 0x7f7f7f7f);
    dp[0] = 0;
    for(int i = 0; i < (1 << n); i++)
        for(int k = 1; k <= n; k++)
            for(int s = k; s <= n; s++)
                if(k != s)
                    dp[i | line[k][s]] = min(dp[i | line[k][s]], dp[i] + 1);
                else
                    dp[i | (1 << (k - 1))] = min(dp[i | (1 << (k - 1))], dp[i] + 1);
    //注意这里的按位或操作，因为这头猪可能已经被击落了
    cout << dp[(1 << n) - 1] << endl;
    return;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
        work();
    return 0;
}

时间复杂度是 O(Tn^22^n)，只能拿到 75\text{pts}。但是为了更清晰地展示状压 DP 的思路，我没有把优化后的程序放进来。

例题2

USACO 2006 Nov. Gold Corn Fields 牧场的安排

一道非常经典的问题。看完题目就想到了用状压 DP。

我们分行来处理，每一行进行状态压缩，种草则为 1，不种草则为 0。题目有限制条件，所以我们要筛选有效状态，筛选方法见代码。所以我们在数组的下标中用 i 表示“第 i 个有效状态”。

而每一行的决策只与上一行的状态有关，所以我们设计的状态为——用 dp_{i,j} 表示第 i 行状态为 j 的方案数。转移时注意判断与上一行状态的搭配是否合法。

但是我们还要判断这块土地是否贫瘠，有个小 trick：我们把这块土地贫瘠用 1 表示，反之用 0 表示，同样进行状态压缩，如果当前行土地选择状态按位与土地贫瘠状态的结果大于0，则这个方案不合法。详见代码：

#include<iostream>
using namespace std;
const int mod = 1e8;
int m, n, cnt;
const int maxn = 14;
int field[maxn], a[1 << maxn];
int f[maxn][1 << maxn];

int main()
{
    cin >> m >> n;
    for(int i = 0; i < (1 << n); i++)
        if((i & (i << 1)) == 0)  //判断是否有相邻且同时选择的土地
            a[++cnt] = i; 
    for(int i = 1; i <= m; i++)
    {
        int x = 0;
        for(int j = 1; j <= n; j++)
        {
            int val;
            cin >> val;
            x = (x << 1) + (val ^ 1);
        }
        field[i] = x;
    }
    for(int i = 1; i <= cnt; i++)
        if((a[i] & field[1]) == 0)  //判断是否有贫瘠的土地被选择了
            f[1][i] = 1;
    for(int i = 2; i <= m; i++)
    {
        for(int j = 1; j <= cnt; j++)
            for(int l = 1; l <= cnt; l++)
                if((a[j] & a[l]) == 0 && (a[j] & field[i]) == 0)
                //判断与上一行的土地有没有相邻的且有没有选贫瘠的土地
                    f[i][j] = (f[i][j] + f[i - 1][l]) % mod;
    }
    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        ans = (ans + f[m][i]) % mod;
    cout << ans << endl;
    return 0;
}

例题3

一本通 5.4 练习 1 涂抹果酱

谁说状态压缩一定是二进制？

我们同样进行状态压缩，只不过数是三进制，为了方便用 string 存储，用和上一题大同小异的做法。然后……就没有然后了。

#include<iostream>
#include<string>
using namespace std;
int n, m, k, cnt = 0;
const int mod = 1e6, maxn = 10005;
string a[245], tmp, spe;
int f[maxn][245], idx;

void dfs(int x, char last)
{
    if(x > m)
    {
        a[++cnt] = tmp;
        if(tmp == spe)
            idx = cnt;
        return;
    }
    for(char i = '1'; i <= '3'; i++)
    {
        if(i == last)
            continue;
        tmp += i;
        dfs(x + 1, i);
        tmp.erase(x - 1, 1);
    }
    return;
}

bool judge(string x, string y)
{
    for(int i = 0; i < m; i++)
        if(x[i] == y[i])
            return false;
    return true;
}

int main()
{
    cin >> n >> m >> k;
    char last = '#';
    for(int i = 1; i <= m; i++)
    {
        char c;
        cin >> c;
        if(c == last)
        {
            cout << 0 << endl;
            return 0;
        }
        last = c;
        spe += c;
    }
    dfs(1, '#');
    for(int i = 1; i <= cnt; i++)
        if(k != 1 || i == idx)
            f[1][i] = 1;
    for(int i = 2; i <= n; i++)
        for(int l = 1; l <= cnt; l++)
        {
            if(i == k)
            {
                if(judge(a[idx], a[l]))
                    f[i][idx] = (f[i][idx] + f[i - 1][l]) % mod;
            }
            else for(int j = 1; j <= cnt; j++)
                if(judge(a[l], a[j]))
                    f[i][j] = (f[i][j] + f[i - 1][l]) % mod;
        }
    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        ans = (ans + f[n][i]) % mod;
    cout << ans << endl; 
    return 0;
}

总结

状压 DP 是比较常考的一类动态规划，它的使用情境比较特殊，会有很明显的提示。