Bỏ qua

Plug DP

Định nghĩa

Một số bài toán DP trạng thái nén (State Compression DP) yêu cầu chúng ta ghi lại thông tin về tính liên thông của các trạng thái. Loại bài toán này thường được gọi một cách hình ảnh là DP Cắm (Plug DP) hoặc DP nén trạng thái liên thông. Ví dụ: đếm số đường đi Hamiltonian trên đồ thị lưới, tìm số cách tô màu đen trắng cho bàn cờ sao cho các ô cùng màu tạo thành một khối liên thông, hoặc đếm số cây bao trùm của một đồ thị đặc biệt. Những bài toán này thường yêu cầu chúng ta mã hóa tính liên thông của trạng thái và thảo luận về sự thay đổi tính liên thông trong quá trình chuyển trạng thái.

Giới thiệu

Phủ quân Domino và DP đường bao (Contour Line DP)

Trước khi học Plug DP, hãy cùng ôn lại một bài toán kinh điển.

Ví dụ 「HDU 1400」Mondriaan’s Dream

Đề bài: Cho bàn cờ \(N \times M\), tìm số cách phủ kín bàn cờ bằng các quân domino kích thước \(1 \times 2\) hoặc \(2 \times 1\).

Khi \(N\) hoặc \(M\) không quá lớn, bài toán này có thể giải bằng DP trạng thái nén. Chia giai đoạn theo từng hàng, gọi \(dp(i, s)\) là số cách khi đã xét xong \(i\) hàng đầu tiên và trạng thái của hàng thứ \(i\) là \(s\). Trạng thái \(s\) ở mỗi vị trí biểu thị ô đó có bị hàng trên phủ xuống hay không.

domino

Một cách chia giai đoạn khác là DP theo từng ô, hay còn gọi là DP đường bao. \(dp(i, j, s)\) biểu thị đã xét đến hàng \(i\) cột \(j\), và trạng thái trên đường bao hiện tại là \(s\).

Mặc dù trạng thái tăng thêm một chiều \((j)\), nhưng độ phức tạp chuyển trạng thái giảm xuống còn \(O(1)\), vì vậy tổng độ phức tạp không đổi. Gọi \(f_0\) là trạng thái giai đoạn hiện tại, \(f_1\) là trạng thái giai đoạn tiếp theo, \(u = f_0(s)\) là giá trị hiện tại, ta có phương trình chuyển trạng thái:

1
2
3
4
5
6
if (s >> j & 1) {       // Nếu đã bị phủ từ trên xuống
  f1[s ^ 1 << j] += u;  // Không đặt thêm gì (ô hiện tại đã kín)
} else {                // Nếu chưa bị phủ
  if (j != m - 1 && (!(s >> j + 1 & 1))) f1[s ^ 1 << j + 1] += u;  // Đặt nằm ngang
  f1[s ^ 1 << j] += u;                                             // Đặt thẳng đứng
}

Cài đặt 
 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
#include <algorithm>
#include <iostream>
using namespace std;
constexpr 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;
  }
}

Thuật ngữ

Giai đoạn: Thứ tự thực thi quy hoạch động, kết quả giai đoạn sau chỉ phụ thuộc vào giai đoạn trước (tính không hệ quả).

Đường bao (Contour Line): Đường ranh giới giữa các ô đã quyết định và các ô chưa quyết định.

contour line

Cắm (Plug): Một ô có "phích cắm" tại một hướng nghĩa là tại hướng đó nó có kết nối với ô kề cạnh.

plug

Mô hình đường đi

Nhiều chu trình (Multiple Circuits)

Ví dụ

Ví dụ 「HDU 1693」Eat the Trees

Đề bài: Tìm số cách dùng một hoặc nhiều chu trình rời nhau để phủ kín các ô không có vật cản trên bàn cờ \(N \times M\).

Nghiêm túc mà nói, bài toán nhiều chu trình chưa hẳn là Plug DP thực thụ, vì ta chỉ cần ghi nhận sự tồn tại của phích cắm (0 hoặc 1) và thực hiện ghép đôi hoặc tạo mới phích cắm theo cặp là đủ.

Lưu ý: Với bàn cờ độ rộng \(m\), đường bao có độ rộng \(m+1\) (gồm \(m\) phích cắm trên và \(1\) phích cắm trái). Khi kết thúc một hàng, phích cắm trái ngoài cùng bên phải là không hợp lệ, ta cần thực hiện thao tác cuộn roll() để chuẩn bị cho hàng tiếp theo.

Mã nguồn ví dụ 
 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
#include <iostream>
using namespace std;
constexpr 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];
    }
    cout << "Case " << Case << ": There are " << f1[0]
         << " ways to eat the trees.\n";
  }
}

Một chu trình duy nhất (Single Circuit)

Ví dụ

Ví dụ 「ASC 16 - Problem F」Pipe Layout

Đề bài: Tìm số cách dùng duy nhất một chu trình để phủ kín bàn cờ \(N \times M\).

Trong bài toán này, nếu chỉ ghi nhận phích cắm tồn tại hay không, ta có thể vô tình tạo ra nhiều chu trình rời nhau. Vì vậy, ta cần phân biệt tính liên thông giữa các phích cắm bằng cách mã hóa trạng thái.

Mã hóa trạng thái

Hai phương pháp phổ biến là biểu diễn bằng dấu ngoặc (bracket) và biểu diễn tối tiểu (minimal representation). Ở đây giới thiệu biểu diễn tối tiểu: dùng mảng độ dài \(m+1\), phích cắm không tồn tại là \(0\), các phích cắm liên thông với nhau được đánh cùng một số hiệu.

Ví dụ, hai trạng thái sau là tương đương: - 0 3 1 0 1 3 - 0 1 2 0 2 1 (Biểu diễn tối tiểu - thứ tự số hiệu xuất hiện từ trái qua phải là nhỏ nhất).

Cài đặt mã hóa 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

Bảng băm thủ công (Handwritten Hash Table)

Vì các trạng thái hợp lệ thường rất thưa thớt, ta nên dùng bảng băm để lưu trữ để tiết kiệm không gian và thời gian.

Cài đặt bảng băm 
1
2
3
4
5
6
7
8
struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];
  void clear() { ... }
  void push(int s) { ... }
  void roll() { ... }
} H[2], *H0, *H1;

Chuyển trạng thái

Quá trình chuyển trạng thái xét ô \((i, j)\) với phích cắm trái \(lt\) và phích cắm trên \(up\). Có các trường hợp chính: 1. Cả \(lt\) và \(up\) đều tồn tại: Hợp nhất hai thành phần liên thông. Nếu chúng đã thuộc cùng một thành phần, chỉ cho phép đóng chu trình nếu đây là ô cuối cùng. 2. Chỉ một trong \(lt\) hoặc \(up\) tồn tại: Kéo dài phích cắm xuống dưới hoặc sang phải. 3. Cả hai đều không tồn tại: Tạo ra một cặp phích cắm mới hướng xuống và hướng sang phải.

Mã nguồn ví dụ 
  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
111
112
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int M = 10;
constexpr int offset = 3, mask = (1 << offset) - 1;
int n, m;
long long ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

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

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

  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;
}

Một đường đi duy nhất (Single Path)

Ví dụ

Ví dụ 「ZOJ 3213」Beautiful Meadow

Đề bài: Cho lưới \(N \times M\) với các ô có trọng số, tìm một đường đi (không nhất thiết là chu trình) sao cho tổng trọng số các ô đi qua là lớn nhất.

Trong bài toán đường đi, trạng thái có thể xuất hiện các phích cắm độc lập (đầu mút đường đi). Ta cần ghi lại số lượng đầu mút đã xuất hiện (không quá 2).

Mã nguồn ví dụ 
  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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <cstring>
#include <iostream>
using namespace std;

template <class T>
bool checkMax(T &a, const T b) {
  return a < b ? a = b, true : false;
}

constexpr int N = 8, M = 8;
constexpr int offset = 3, mask = (1 << offset) - 1;
int A[N + 1][M + 1];
int n, m;
int ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

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

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

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        checkMax(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][3], *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 c, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1[c].push(encode());
}

void init() {
  cin >> n >> m;
  H0 = H[0], H1 = H[1];
  for (int c = 0; c < 3; c++) H1[c].clear();
  d = 0;
  H1[0].push(0);
  memset(A, 0, sizeof(A));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> A[i][j];
}

void solve() {
  ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      checkMax(ans, A[i][j]);  // 需要单独处理一个格子的情况
      if (!A[i][j]) continue;  // 如果有障碍，则跳过，注意这时状态数组不需要滚动
      swap(H0, H1);
      for (int c = 0; c < 3; c++)
        H1[c].clear();  // c 表示生成和消失事件发生的总次数，最多不超过 2 次
      for (int c = 0; c < 3; c++)
        for (int ii = 0; ii < H0[c].sz; ii++) {
          decode(H0[c].state[ii]);
          d = H0[c].key[ii] + A[i][j];
          int lt = b[j], up = b[j + 1];
          bool dn = A[i + 1][j], rt = A[i][j + 1];
          if (lt && up) {
            if (lt == up) {  // 在一条路径问题中，我们不能合并相同的插头。
              // Cannot deploy here...
            } else {  // 有可能参与合并的两者中有独立插头，但是也可以用同样的代码片段处理
              for (int i = 0; i < m + 1; i++)
                if (b[i] == lt) b[i] = up;
              push(c, j, 0, 0);
            }
          } else if (lt || up) {
            int t = lt | up;
            if (dn) {
              push(c, j, t, 0);
            }
            if (rt) {
              push(c, j, 0, t);
            }
            // 一个插头消失的情况，如果是独立插头则意味着消失，如果是成对出现的插头则相当于生成了一个独立插头，
            // 无论哪一类事件都需要将 c + 1。
            if (c < 2) {
              push(c + 1, j, 0, 0);
            }
          } else {
            d -= A[i][j];
            H1[c].push(H0[c].state[ii]);
            d += A[i][j];  // 跳过插头生成，本题中不要求全部覆盖
            if (dn && rt) {  // 生成一对插头
              push(c, j, m, m);
            }
            if (c < 2) {  // 生成一个独立插头
              if (dn) {
                push(c + 1, j, m, 0);
              }
              if (rt) {
                push(c + 1, j, 0, m);
              }
            }
          }
        }
    }
    for (int c = 0; c < 3; c++) H1[c].roll();  // 一行结束，调整轮廓线
  }
  for (int ii = 0; ii < H1[2].sz; ii++) checkMax(ans, H1[2].key[ii]);
  cout << ans << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
  }
}

Mô hình tô màu (Coloring Model)

Bên cạnh mô hình đường đi, còn có mô hình tô màu bàn cờ sao cho các ô cùng màu kề nhau tạo thành các khối liên thông. Thay vì duyệt hướng đường đi, ta duyệt màu cho ô hiện tại.

Ví dụ 「UVa 10572」Black & White

Đề bài

Tô màu đen/trắng cho các ô chưa tô sao cho mọi vùng đen và vùng trắng đều liên thông, đồng thời không có bất kỳ hình vuông \(2 \times 2\) nào cùng một màu.

Mô hình này yêu cầu mã hóa cả màu sắc và tính liên thông trên đường bao.

Mã nguồn ví dụ 
  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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
using T_state = long long;
using T_key = int;
constexpr int N = 8;
int n, m;
char A[N + 1][N + 1], B[N + 1][N + 1];
constexpr int Offset = 5, Mask = (1 << Offset) - 1;
int c[N + 2];
int b[N + 2], bb[N + 3];

T_state encode() {
  T_state 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]] << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

constexpr int Prime = 9979, MaxSZ = 1 << 20;

template <class T_state, class T_key>
struct hashTable {
  int head[Prime];
  int next[MaxSZ], sz;
  T_state state[MaxSZ];
  T_key key[MaxSZ];
  int pre[MaxSZ];

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

  void push(T_state s, T_key d, T_state u) {
    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, pre[sz] = u;
    next[sz] = head[x], head[x] = sz++;
  }

  void roll() {
    for (int ii = 0; ii < sz; ii++) state[ii] <<= Offset;
  }
};

hashTable<T_state, T_key> _H, H[N][N], *H0, *H1;

bool ok(int i, int j, int cc) {
  if (cc == c[j + 1]) return true;
  int up = b[j + 1];
  if (!up) return true;
  int c1 = 0, c2 = 0;
  for (int i = 0; i < m + 1; i++)
    if (i != j + 1) {
      if (b[i] == b[j + 1]) {  // 连通性相同，颜色一定相同
        assert(c[i] == c[j + 1]);
      }
      if (c[i] == c[j + 1] && b[i] == b[j + 1]) ++c1;
      if (c[i] == c[j + 1]) ++c2;
    }
  if (!c1) {               // 如果会生成新的封闭连通块
    if (c2) return false;  // 如果轮廓线上还有相同的颜色
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

void trans(int i, int j, int u, int cc) {
  decode(H0->state[u]);
  int lf = j ? c[j - 1] : -1, lu = b[j] ? c[j] : -1,
      up = b[j + 1] ? c[j + 1] : -1;  // 没有颜色也是颜色的一种！
  if (lf == cc && up == cc) {         // 合并
    if (lu == cc) return;             // 2x2 子矩形相同的情况
    int lf_b = b[j - 1], up_b = b[j + 1];
    for (int i = 0; i < m + 1; i++)
      if (b[i] == up_b) {
        b[i] = lf_b;
      }
    b[j] = lf_b;
  } else if (lf == cc || up == cc) {  // 继承
    if (lf == cc)
      b[j] = b[j - 1];
    else
      b[j] = b[j + 1];
  } else {                                             // 生成
    if (i == n - 1 && j == m - 1 && lu == cc) return;  // 特判
    b[j] = m + 2;
  }
  c[j] = cc;
  if (!ok(i, j, cc)) return;  // 判断是否会因生成封闭的连通块导致不合法
  H1->push(encode(), H0->key[u], u);
}

void init() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> A[i];
}

void solve() {
  H1 = &_H, H1->clear(), H1->push(0, 1, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      H0 = H1, H1 = &H[i][j], H1->clear();
      for (int u = 0; u < H0->sz; u++) {
        if (A[i][j] == '.' || A[i][j] == '#') trans(i, j, u, 0);
        if (A[i][j] == '.' || A[i][j] == 'o') trans(i, j, u, 1);
      }
    }
    H1->roll();
  }
}

void print() {
  T_key z = 0;
  int u;
  for (int i = 0; i < H1->sz; i++) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    for (int i = n - 1; i >= 0; i--) {
      B[i][m] = 0;
      for (int j = m - 1; j >= 0; j--) {
        decode(H[i][j].state[u]);
        int cc = j == m - 1 ? c[j + 1] : c[j];
        B[i][j] = cc ? 'o' : '#';
        u = H[i][j].pre[u];
      }
    }
    for (int i = 0; i < n; i++) cout << B[i] << '\n';
  }
  cout << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
    print();
  }
}

Mô hình đồ thị và Thực chiến

Plug DP còn áp dụng cho các bài toán về cây bao trùm đặc biệt hoặc bài toán xây tường ngăn cách.

Ví dụ 「HDU 4113」Construct the Great Wall

Đề bài

Xây dựng một chu trình kín để ngăn cách tất cả các ô ký hiệu x và o.

Bài toán này có thể giải bằng cách chạy Plug DP trên các điểm giao của lưới. Ta cần duy trì thêm thông tin ô hiện tại nằm trong hay ngoài chu trình (sử dụng quy tắc tia sáng - số lần cắt phích cắm đứng).

Ghi chú

Plug DP là kỹ thuật có độ khó lập trình cao, thường xuất hiện trong các kỳ thi OI/ACM nâng cao. Tài liệu kinh điển nhất là luận văn năm 2008 của Chen Danqi (Trần Đan Kỳ) về "Bài toán quy hoạch động dựa trên nén trạng thái liên thông".

Các biến thể của Phủ Domino

  • Nếu \(M=2\), bài toán tương đương dãy Fibonacci.
  • Nếu \(M \le 10, N \le 10^9\), dùng nhân ma trận để tăng tốc.
  • Nếu \(N, M \le 100\), dùng thuật toán FKT để tính số bộ ghép hoàn hảo của đồ thị phẳng.
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply