投稿
  1. 高性能架构探索首页
  2. C/C++

状态压缩

admin • • C/C++ • 阅读 136

参考博客：状态压缩动态规划 状压DP

什么是状态压缩

　　状态压缩，是用计算机二进制来表示一组数的状态。比如一行路灯的开关状态：

路灯 开 关 开 开 关 开 关 开 开
二进制状态 1 0 1 1 0 1 0 1 1

　　于是我们就可以用一个数来表示这整行路灯的状态： \((101101011)_2=(363)_{10}\) ， \(363\) 即可表示这排路灯的开关状态。
　　一排有 \(n\) 个路灯，一共就有 \(2^{n}-1\) （即 \((\underline{11\cdots 1}_{n\times 1})_2\) ）种状态。（这也意味着，当一个多维的图摆在我们面前，其行和列的范围不一致时，比如 \(1\leqslant n\leqslant1000\) ， \(1\leqslant m\leqslant 10\)，这就意味着对于列，完全可以压缩成 \(1023\) 种状态的集合，这种题目用状压的概率很大）。
　　要处理路灯开关状态的变化，同样可以通过二进制数的操作来完成，比如：我们将右起第三个灯打开，即将状态变为 \((101101111)_2\) ，只要通过位运算就可以完成。设原状态是 \(i\) （ \(i\) 是整型数），则新状态就是 i|(1<<2) 。
　　实际运用中，常见的状态转移有几种：（原状态记为 \(state\) ）

  • 右起（以下不特别说明均是从零开始计）第 \(i\) 位从 \(0\) 变为 \(1\) ： state|=(1<<i)
  • 右起第 \(i\) 位从 \(1\) 变为 \(0\)： state^=(1<<i)
  • 检验右起第 \(i\) 位是不是 \(0\) ： state&(1<<i)==0
  • 要求两个 \(1\) 之间至少隔一个 \(0\) ： (state&(state<<1))==0
  • 要求两个 \(1\) 之间至少隔两个 \(0\) ： ((state&(state<<1))==0)&&((state&(state<<2))==0)
  • 去掉状态中最右边的 \(1\) ： state&=(state-1)

\(\cdots\cdots\)，想到再写。

状态压缩+BFS

P2622 关灯问题II

　　首先要注意到，这道题目的 \(m\) 上限较大，但 \(n\) 最大也只有 \(10\) ，具备状态压缩的条件。
　　灯的开与关是一组二元状态，可以用 \(0\) 和 \(1\) 来表示。开关对一盏灯的作用有三种，我们写一下状态转移的方程（为了方便起见，灯的序号应从 \(0\) 开始，即 a[i][j] 从 \(0\) 开始存数：

  • a[i][j]=1 即 if(state&(1<<j)) state^=(1<<j)
  • a[i][j]=-1 即 state|=(1<<j)
  • a[i][j]=0 不需要改变第 \(j\) 位的数

　　我们来分析一下这个题目的思路。要求从初始状态（全 \(1\) ，或 (1<<n)-1），经过最少操作变为全 \(0\) 状态，类似于最短路问题，考虑使用广度优先搜索（BFS）算法。最坏情况下队列中留有 \(2^n\) 个状态，每一个状态遍历完所有可能的转移情况需要 \(n\times m\) 次操作，所以整个程序的复杂度为 \(\Theta(NM\cdot 2^N)\)，暴力但可行（逃）。

#include <bits/stdc++.h>
using namespace std;

int read()
{
    int ans = 0, flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        ans = (ans << 1) + (ans << 3) + (ch ^ '0');
        ch = getchar();
    }
    return flag > 0 ? ans : ~ans + 1;
};
#define read read() //以上为常规内容
#define MAXN 10
#define MAXM 105

struct node
{
    int state;
    int step;
};

int n, m, a[MAXM][MAXN];
bool vis[1 << MAXN] = {0};

void bfs(int initial_state) //BFS板子
{
    queue<node> q;
    q.push({initial_state, 0});
    vis[initial_state] = 1;
    while (!q.empty())
    {
        node vs = q.front();
        q.pop();
        for (int i = 1; i <= m; i++)
        {
            int current_state = vs.state;
            for (int j = 0; j < n; j++) //需要对每个灯做状态转移的操作，故每个按钮对应 n 次操作
            {
                switch (a[i][j])
                {
                case 1:
                    if (current_state & (1 << j))
                        current_state ^= (1 << j);
                    break;

                case -1:
                    current_state |= (1 << j);
                    break;

                default:
                    break;
                }
            }
            if (vis[current_state])
                continue;
            node ve = {current_state, vs.step + 1};
            if (ve.state == 0)
            {
                printf("%d\n", ve.step);
                exit(0);
            }
            q.push(ve);
            vis[current_state] = 1;
        }
    }
}

int main()
{
    n = read, m = read;
    int init = (1 << n) - 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = read;
    bfs(init);
    puts("-1");
    return 0;
}

状态压缩+DP

　　状态压缩在动态规划问题下的应用也很广泛，它把一个本该用线性表表示的状态集合处理成了一个数，这使得对状态集合的动态规划变得可行。不过我们在上一段也说过了，状态压缩比较暴力，因为状态数是幂级的，尤其是放到 \(dp\) 数组里的时候，空间复杂度会变得很大。好在，需要用到状压的动归问题，常常在一行，即一个状态集合，里给出了限制条件，使得很多的状态完全不符合条件，这对降低复杂度大有益处。
　　先不用减少状态的处理技巧，我们看一道例题：

P1879 【USACO06NOV】Corn Fields G

#include <bits/stdc++.h>
using namespace std;

int read()
{
    int ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        ans = (ans << 1) + (ans << 3) + (ch ^ '0');
        ch = getchar();
    }
    return ans;
};
#define read read() //以上为常规内容

#define MAX 1 << 12
#define MOD 100000000

int n, m, x, graph[15] = {0}, valid[MAX] = {0}, dp[15][MAX] = {0};

int main()
{
    m = read, n = read;
    int max_state = (1 << n) - 1;
    //由于草地的状态也是以整行来考虑的，同样可以状态压缩，而不需要像BFS那道题一样存成二维数组
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            x = read;
            graph[i] = (graph[i] << 1) + x;
        }
    for (int i = 0; i <= max_state; i++)    //预处理 - 不符合“不相邻”要求的
        if ((i & (i << 1)) == 0)
            valid[i] = 1;
    for (int i = 0; i <= max_state; i++)    //预处理 - 第一行
        if (valid[i] && ((i & graph[1]) == i))
            dp[1][i] = 1;
    for (int i = 2; i <= m; i++)    //开始递推
        for (int j = 0; j <= max_state; j++)
            if (valid[j] && ((j & graph[i]) == j))
                for (int k = 0; k <= max_state; k++)
                    if ((k & j) == 0)
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
    int ans = 0;
    for (int i = 0; i <= max_state; i++)    //最后一行每种状态下都有几种，求和
        ans = (ans + dp[m][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

　　那么怎么用上这个技巧呢？我们注意到本题有一个预处理：

for (int i = 0; i <= max_state; i++)    //预处理 - 不符合“不相邻”要求的
    if ((i & (i << 1)) == 0)
        valid[i] = 1;

　　我们其实已经求出了所有符合“不相邻”要求的状态，那么在下面的遍历中，就不需要遍历 \(0\sim max\_state\) 所有情况，而只需要遍历符合要求的情况就可以了。做一点小改动：

for (int i = 0; i <= max_state; i++)
    if ((i & (i << 1)) == 0)
        valid[cnt++] = i;

　　在实际做题的时候，可以在这个循环做完后打印出 \(cnt\) 的值，本题 \(n\) 最大只有 \(12\) ，对应 \(cnt\) 最大只有 \(377\) ，在开数组的时候就也可以适当地减小一些。下面是完整程序。

#include <bits/stdc++.h>
using namespace std;

int read()
{
    int ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        ans = (ans << 1) + (ans << 3) + (ch ^ '0');
        ch = getchar();
    }
    return ans;
};
#define read read()

#define MAX 380
#define MOD 100000000

int n, m, x, cnt = 0, graph[15] = {0}, valid[MAX] = {0}, dp[15][MAX] = {0};

int main()
{
    m = read, n = read;
    int max_state = (1 << n) - 1;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            x = read;
            graph[i] = (graph[i] << 1) + x;
        }
    for (int i = 0; i <= max_state; i++)
        if ((i & (i << 1)) == 0)
            valid[cnt++] = i;
    for (int i = 0; i < cnt; i++)
        if ((valid[i] & graph[1]) == valid[i])
            dp[1][i] = 1;
    for (int i = 2; i <= m; i++)
        for (int j = 0; j < cnt; j++)
            if ((valid[j] & graph[i]) == valid[j])
                for (int k = 0; k < cnt; k++)
                    if ((valid[k] & valid[j]) == 0)
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
    int ans = 0;
    for (int i = 0; i <= max_state; i++)
        ans = (ans + dp[m][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

　　这道题的数据量较小，且“不相邻”的状态量也不小，所以这样的技巧优势不大（ 先后两种写法测试结果分别是 \(37ms/824KB\) 与 \(27ms/712KB\) ）。不过这种技巧在某些题目中则有着不错的效果，尤其是在那些要求比较苛刻的题目中对算法的优化还是很明显的。

P2704 【NOI2001】炮兵阵地

　　来看一道稍微复杂一点的题目。动态规划的思路其实还是差不多的，只是预处理需要前两行，而递推也要多一层循环。不过这也意味着复杂度会增加，尝试用减少状态量的技巧来优化算法。

#include <stdio.h>

#define MAX 61 //cnt最多只有60。。。

int n, m, cnt = 0;
long long dp[105][MAX][MAX]; //[行数][该行对应状态][上一行对应状态]
int judge[105][MAX];         //合法状态是否可以放入相应行
int map[105];                //按行存放图的状态
int valid[MAX];              //合法的状态
int num[MAX];                //每种合法状态对应的炮兵数

int main()
{
    char ch[15];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", ch);
        for (int j = 0; j < m; j++)
        {
            if (ch[j] == 'P')
                map[i] = (map[i] << 1) + 1;
            else
                map[i] = map[i] << 1;
        }
    }
    int max_state = (1 << m) - 1;
    for (int i = 0; i <= max_state; i++)
        if (((i << 1) & i) == 0 && ((i << 2) & i) == 0)
        {
            valid[++cnt] = i; //存入合法的状态，从1到cnt
            int temp = i;
            while (temp)
            {
                if (temp & 1)
                    num[cnt]++;
                temp >>= 1;
            }
        }
    for (int i = 1; i <= cnt; i++) //第一行预处理
        if ((valid[i] & map[1]) == valid[i])
        {
            judge[1][i] = 1;
            dp[1][i][0] = num[i];
        }
    for (int i = 1; i <= cnt; i++) //第二行预处理
        if ((valid[i] & map[2]) == valid[i])
        {
            judge[2][i] = 1;
            for (int j = 1; j <= cnt; j++)
                if (judge[1][j] && ((valid[i] & valid[j]) == 0))
                    dp[2][i][j] = dp[2][i][j] >= dp[1][j][0] + num[i] ? dp[2][i][j] : dp[1][j][0] + num[i];
        }
    for (int i = 3; i <= n; i++)
        for (int j = 1; j <= cnt; j++)
            if ((valid[j] & map[i]) == valid[j])
            { //当前行是状态j
                judge[i][j] = 1;
                for (int k = 1; k <= cnt; k++)
                    if (judge[i - 2][k] && ((valid[j] & valid[k]) == 0)) //两行之上是状态k
                        for (int p = 1; p <= cnt; p++)
                            if (judge[i - 1][p] && ((valid[j] & valid[p]) == 0) && ((valid[k] & valid[p]) == 0)) //一行之上是状态p
                                dp[i][j][p] = dp[i][j][p] >= dp[i - 1][p][k] + num[j] ? dp[i][j][p] : dp[i - 1][p][k] + num[j];
            }
    long long ans = 0;
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            ans = ans >= dp[n][i][j] ? ans : dp[n][i][j];
    printf("%lld\n", ans);
    return 0;
}

　　这种方法优势在哪？由于每两个炮兵之间至少要空出两格，所以状态量大大减少， \(M=10\) 的时候，也只有 \(60\) 种状态符合要求，从而时间、空间消耗都能少很多。本题开启 \(O_2\) 后，仅用了 \(109ms/3.40MB\) ，尤其是在内存使用上有了很大的优化。

原文链接: https://www.cnblogs.com/guapiii/p/StateCompression.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    状态压缩

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360104

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午1:06
下一篇 2023年3月2日 下午1:06

相关推荐