跳转至

插头 DP

定义

有些 状压 DP 问题要求我们记录状态的连通性信息,这类问题一般被形象的称为插头 DP 或连通性状态压缩 DP。例如格点图的哈密顿路径计数,求棋盘的黑白染色方案满足相同颜色之间形成一个连通块的方案数,以及特定图的生成树计数等等。这些问题通常需要我们对状态的连通性进行编码,讨论状态转移过程中连通性的变化。

引入

骨牌覆盖与轮廓线 DP

温故而知新,在开始学习插头 DP 之前,不妨先让我们回顾一个经典问题。

例题 「HDU 1400」Mondriaan’s Dream

题目大意:在 \(N\times M\) 的棋盘内铺满 \(1\times 2\)\(2\times 1\) 的多米诺骨牌,求方案数。

\(n\)\(m\) 规模不大的时候,这类问题可以使用 状压 DP 解决。逐行划分阶段,设 \(dp(i,s)\) 表示当前已考虑过前 \(i\) 行,且第 \(i\) 行的状态为 \(s\) 的方案数。这里的状态 \(s\) 的每一位可以表示这个这个位置是否已被上一行覆盖。

domino

另一种划分阶段的方法是逐格 DP,或者称之为轮廓线 DP。\(dp(i,j,s)\) 表示已经考虑到第 \(i\) 行第 \(j\) 列,且当前轮廓线上的状态为 \(s\) 的方案数。

虽然逐格 DP 中我们的状态增加了一个维度,但是转移的时间复杂度减少为 \(O(1)\),所以时间复杂度未变。我们用 \(f_0\) 表示当前阶段的状态,用 \(f_1\) 表示下一阶段的状态,\(u = f_0(s)\) 表示当前枚举的函数值,那么有如下的状态转移方程:

1
2
3
4
5
6
if (s >> j & 1) {       // 如果已被覆盖
  f1[s ^ 1 << j] += u;  // 不放
} else {                // 如果未被覆盖
  if (j != m - 1 && (!(s >> j + 1 & 1))) f1[s ^ 1 << j + 1] += u;  // 横放
  f1[s ^ 1 << j] += u;                                             // 竖放
}

观察到这里不放和竖放的方程可以合并。

实现
 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
#include <bits/stdc++.h>
using namespace std;
const int N = 11;
long long f[2][1 << N], *f0, *f1;
int n, m;

int main() {
  while (cin >> n >> m && n) {
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << m), 0);
    f1[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        swap(f0, f1);
        fill(f1, f1 + (1 << m), 0);
#define u f0[s]
        for (int s = 0; s < 1 << m; ++s)
          if (u) {
            if (j != m - 1 && (!(s >> j & 3))) f1[s ^ 1 << j + 1] += u;  // 横放
            f1[s ^ 1 << j] += u;  // 竖放或不放
          }
      }
    }
    cout << f1[0] << endl;
  }
}
习题 「SRM 671. Div 1 900」BearDestroys

题目大意:给定 \(n\times m\) 的矩阵,每个格子有 ES。 对于一个矩阵,有一个计分方案。按照行优先的规则扫描每个格子,如果这个格子之前被骨牌占据,则 skip。 否则尝试放多米诺骨牌。如果放骨牌的方向在矩阵外或被其他骨牌占据,则放置失败,切换另一种方案或 skip。 如果是 E 则优先放一个 \(1\times 2\) 的骨牌, 如果是 S 则优先放一个 \(2\times 1\) 的骨牌。 一个矩阵的得分为最后放的骨牌数。 问所有 \(2^{nm}\) 种矩阵的得分的和。

术语

阶段:动态规划执行的顺序,后续阶段的结果只与前序阶段的结果有关(无后效性)。很多 DP 问题可以有多种划分阶段的方式。例如在背包问题中,我们通常既可以按照物品划分阶段,也可以按照背包容量划分阶段(外层循环先枚举什么)。而在多米诺骨牌问题中,我们可以按照行、列、格子以及对角线等特征划分阶段。

轮廓线:已决策状态和未决策状态的分界线。

contour line

插头:一个格子某个方向的插头存在,表示这个格子在这个方向与相邻格子相连。

plug

路径模型

多条回路

例题

例题 「HDU 1693」Eat the Trees

题目大意:求用若干条回路覆盖 \(N\times M\) 棋盘的方案数,有些位置有障碍。

严格来说,多条回路问题并不属于插头 DP,因为我们只需要和上面的骨牌覆盖问题一样,记录插头是否存在,然后成对的合并和生成插头就可以了。

注意对于一个宽度为 \(m\) 的棋盘,轮廓线的宽度为 \(m+1\),因为包含 \(m\) 个上插头,和 \(1\) 个左插头。注意,当一行迭代完成之后,最右边的左插头通常是不合法的状态,同时我们需要补上下一行第一个左插头,这需要我们调整当前轮廓线的状态,通常是所有状态进行左移,我们把这个操作称为滚动 roll()

例题代码
 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
#include <bits/stdc++.h>
using namespace std;
const int N = 11;
long long f[2][1 << (N + 1)], *f0, *f1;
int n, m;

int main() {
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    cin >> n >> m;
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << m + 1), 0);
    f1[0] = 1;  // 初始化
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        bool bad;
        cin >> bad;
        bad ^= 1;
        swap(f0, f1);
        fill(f1, f1 + (1 << m + 1), 0);
        for (int s = 0; s < 1 << m + 1; ++s)  // 具体的dp转移,上面都是初始化
          if (f0[s]) {
            bool lt = s >> j & 1, up = s >> j + 1 & 1;
            if (bad) {
              if (!lt && !up) f1[s] += f0[s];
            } else {
              f1[s ^ 3 << j] += f0[s];
              if (lt != up) f1[s] += f0[s];
            }
          }
      }
      swap(f0, f1);
      fill(f1, f1 + (1 << m + 1), 0);
      for (int s = 0; s < 1 << m; ++s) f1[s << 1] = f0[s];
    }
    printf("Case %d: There are %lld ways to eat the trees.\n", Case, f1[0]);
  }
}

习题

习题 「ZJU 4231」The Hive II

题目大意:同上题,但格子变成了六边形。

一条回路

例题

例题 「Andrew Stankevich Contest 16 - Problem F」Pipe Layout

题目大意:求用一条回路覆盖 \(N\times M\) 棋盘的方案数。

在上面的状态表示中我们每合并一组连通的插头,就会生成一条独立的回路,因而在本题中,我们还需要区分插头之间的连通性(出现了!)。这需要我们对状态进行额外的编码。

状态编码

通常的编码方案有括号表示和最小表示,这里着重介绍泛用性更好的最小表示。我们用长度 \(m+1\) 的整形数组,记录轮廓线上每个插头的状态,\(0\) 表示没有插头,并约定连通的插头用相同的数字进行标记。

那么下面两组编码方式表示的是相同的状态:

  • 0 3 1 0 1 3
  • 0 1 2 0 2 1

我们将相同的状态都映射成字典序最小表示,例如在上例中的 0 1 2 0 2 1 就是一组最小表示。

我们用 b[] 数组表示轮廓线上插头的状态。bb[] 表示在最小表示的编码的过程中,每个数字被映射到的最小数字。注意 \(0\) 表示插头不存在,不能被映射成其他值。

代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= offset;
    s |= bi;
  }
  return s;
}

void decode(int s) {
  REP(i, m + 1) {
    b[i] = s & mask;
    s >>= offset;
  }
}

我们注意到插头总是成对出现,成对消失的。因而 0 1 2 0 1 2 这样的状态是不合法的。合法的状态构成一组括号序列,实际中合法状态可能是非常稀疏的。

手写哈希

在一些 状压 DP 的问题中,合法的状态可能是稀疏的(例如本题),为了优化时空复杂度,我们可以使用哈希表存储合法的 DP 状态。对于 C++ 选手,我们可以使用 std::unordered_map,当然也可以直接手写,这样可以灵活的将状态转移函数也封装于其中。

代码实现
 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
const int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  inline void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  inline void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() { REP(i, sz) state[i] <<= offset; }
} H[2], *H0, *H1;

上面的代码中:

  • MaxSZ 表示合法状态的上界,可以估计,也可以预处理出较为精确的值。
  • Prime 一个小于 MaxSZ 的大素数。
  • head[] 表头节点的指针。
  • next[] 后续状态的指针。
  • state[] 节点的状态。
  • key[] 节点的关键字,在本题中是方案数。
  • clear() 初始化函数,和手写邻接表类似,我们只需要初始化表头节点的指针。
  • push() 状态转移函数,其中 d 是一个全局变量(偷懒),表示每次状态转移所带来的增量。如果找到的话就 +=,否则就创建一个状态为 s,关键字为 d 的新节点。
  • roll() 迭代完一整行之后,滚动轮廓线。

关于哈希表的复杂度分析,以及开哈希和闭哈希的不同,可以参见 《算法导论》 中关于散列表的相关章节。

状态转移

代码实现
 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
REP(ii, H0->sz) {
  decode(H0->state[ii]);                  // 取出状态,并解码
  d = H0->key[ii];                        // 得到增量 delta
  int lt = b[j], up = b[j + 1];           // 左插头,上插头
  bool dn = i != n - 1, rt = j != m - 1;  // 下插头,右插头
  if (lt && up) {                         // 如果左、上均有插头
    if (lt == up) {                       // 来自同一个连通块
      if (i == n - 1 &&
          j == m - 1) {  // 只有在最后一个格子时,才能合并,封闭回路。
        push(j, 0, 0);
      }
    } else {  // 否则,必须合并这两个连通块,因为本题中需要回路覆盖
      REP(i, m + 1) if (b[i] == lt) b[i] = up;
      push(j, 0, 0);
    }
  } else if (lt || up) {  // 如果左、上之中有一个插头
    int t = lt | up;      // 得到这个插头
    if (dn) {             // 如果可以向下延伸
      push(j, t, 0);
    }
    if (rt) {  // 如果可以向右延伸
      push(j, 0, t);
    }
  } else {           // 如果左、上均没有插头
    if (dn && rt) {  // 生成一对新插头
      push(j, m, m);
    }
  }
}
例题代码
  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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
const int M = 10;
const int offset = 3, mask = (1 << offset) - 1;
int n, m;
long long ans, d;
const int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  inline void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  inline void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() {
    for (int i = 0; i < sz; i++) state[i] <<= offset;
  }
} H[2], *H0, *H1;

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= offset;
    s |= bb[b[i]];
  }
  return s;
}

void decode(int s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & mask;
    s >>= offset;
  }
}

void push(int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1->push(encode());
}

int main() {
  cin >> n >> m;
  if (m > n) swap(n, m);
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 1;
  H1->push(0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      swap(H0, H1);
      H1->clear();
      for (int ii = 0; ii < (H0->sz); ii++) {
        decode(H0->state[ii]);
        d = H0->key[ii];
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            if (i == n - 1 && j == m - 1) {
              push(j, 0, 0);
            }
          } else {
            for (int i = 0; i < m + 1; i++)
              if (b[i] == lt) b[i] = up;
            push(j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(j, t, 0);
          }
          if (rt) {
            push(j, 0, t);
          }
        } else {
          if (dn && rt) {
            push(j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  assert(H1->sz <= 1);
  cout << (H1->sz == 1 ? H1->key[0] : 0) << endl;
}

习题

习题 「Ural 1519」Formula 1

题目大意:求用一条回路覆盖 \(N\times M\) 棋盘的方案数,有些位置有障碍。

习题 「USACO 5.4.4」Betsy's Tours

题目大意:一个 \(N\times N\) 的方阵(\(N\le 7\)),求从左上角出发到左下角结束经过每个格子的路径总数。虽然是一条路径,但因为起点和终点固定,可以转化为一条回路问题。

习题 「POJ 1739」Tony's Tour

题目大意:一个 \(N\times M\) 的棋盘,求从左下角出发到右下角结束经过每个格子的路径总数,有些位置有障碍。

习题 「USACO 6.1.1」Postal Vans

题目大意:求用一条有向回路覆盖 \(4\times N\) 的棋盘的方案数,需要高精度。

习题 「ProjectEuler 393」Migrating ants

题目大意:用多条回路覆盖 \(n\times n\) 的方阵,每个有 \(m\) 条回路的方案对答案的贡献是 \(2^m\),求所有方案的贡献和。

一条路径

例题

例题 「ZOJ 3213」Beautiful Meadow

题目大意:一个 \(N\times M\) 的方阵(\(N,M\le 8