跳转至

插頭 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\) 的矩陣，每個格子有 E 或 S。 對於一個矩陣，有一個計分方案。按照行優先的規則掃描每個格子，如果這個格子之前被骨牌佔據，則 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 3466」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];

  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() { 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];

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

習題

習題 「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\) 的棋盤的方案數，需要高精度。

習題 「HNOI 2007」神奇遊樂園

題目大意：給定一個 \(n\times m\) 的網格圖，每格內有一個權值，求一個任意一個迴路，最大化經過的權值和。

習題 「ProjectEuler 393」Migrating ants

題目大意：用多條迴路覆蓋 \(n\times n\) 的方陣，每個有 \(m\) 條迴路的方案對答案的貢獻是 \(2^m\)，求所有方案的貢獻和。

一條路徑

例題

例題 「ZOJ 3213」Beautiful Meadow

題目大意：一個 \(N\times M\) 的方陣（\(N,M\le 8\)），每個格點有一個權值，求一段路徑，最大化路徑覆蓋的格點的權值和。

本題是標準的一條路徑問題，在一條路徑問題中，編碼的狀態中還會存在不能配對的獨立插頭。需要在狀態轉移函數中，額外討論獨立插頭的生成、合併與消失的情況。獨立插頭的生成和消失對應着路徑的一端，因而這類事件不會發生超過兩次（一次生成一次消失，或者兩次生成一次合併），否則最終結果一定會出現多個連通塊。

我們需要在狀態中額外記錄這類事件發生的總次數，可以將這個信息編碼進狀態裏（注意，類似這樣的額外信息在調整輪廓線的時候，不需要跟着滾動），當然也可以在 hashTable 數組的外面加維。下面的範例程序中我們選擇後者。

狀態轉移

代碼實現 
 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
REP(i, n) {
  REP(j, m) {
    checkMax(ans, A[i][j]);  // 需要單獨處理一個格子的情況
    if (!A[i][j]) continue;  // 如果有障礙，則跳過，注意這時狀態數組不需要滾動
    swap(H0, H1);
    REP(c, 3)
    H1[c].clear();  // c 表示生成和消失事件發生的總次數，最多不超過 2 次
    REP(c, 3) REP(ii, H0[c].sz) {
      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 {  // 有可能參與合併的兩者中有獨立插頭，但是也可以用同樣的代碼片段處理
          REP(i, m + 1) 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);
          }
        }
      }
    }
  }
  REP(c, 3) H1[c].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
 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
#include <bits/stdc++.h>
using namespace std;

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

const int N = 8, M = 8;
const int offset = 3, mask = (1 << offset) - 1;
int A[N + 1][M + 1];
int n, m;
int ans, d;
const 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();
  }
}

習題

習題 「BZOJ 2310」ParkII

題目大意：\(m\times n\) 的棋盤，每個格點有一個權值，求一條路徑覆蓋，最大化路徑經過的點的權值和。

習題 「NOI 2010 Day2」旅行路線

題目大意：\(n\times m\) 的棋盤，棋盤的每個格子有一個 01 權值 T[x][y]，要求尋找一個路徑覆蓋，滿足：

  • 第 i 個參觀的格點 (x, y)，滿足 T[x][y]= L[i]
  • 路徑的一端在棋盤的邊界上

求可行的方案數。

染色模型

除了路徑模型之外，還有一類常見的模型，需要我們對棋盤進行染色，相鄰的相同顏色節點被視為連通。在路徑類問題中，狀態轉移的時候我們枚舉當前路徑的方向，而在染色類問題中，我們枚舉當前節點染何種顏色。在染色模型中，狀態中處在相同連通性的節點可能不止兩個。但總體來説依然大同小異。我們不妨來看一個經典的例題。

例題「UVa 10572」Black & White

例題 「UVa 10572」Black & White

題目大意：在 \(N\times M\) 的棋盤內對未染色的格點進行黑白染色，要求所有黑色區域和白色區域連通，且任意一個 \(2\times 2\) 的子矩形內的顏色不能完全相同（例如下圖中的情況非法），求合法的方案數，並構造一組合法的方案。

black_and_white1

狀態編碼

我們先考慮狀態編碼。不考慮連通性，那麼就是 SGU 197. Nice Patterns Strike Back，不難用 狀壓 DP 直接解決。現在我們需要在狀態中同時體現顏色和連通性的信息，考察輪廓線上每個位置的狀態，二進制的每 Offset 位描述輪廓線上的一個位置，因為只有黑白兩種顏色，我們用最低位的奇偶性表示顏色，其餘部分示連通性。

考慮第一行上面的節點，和第一列左側節點，如果要避免特判的話，可以考慮引入第三種顏色區分它們，這裏我們觀察到這些邊界狀態的連通性信息一定為 0，所以不需要對第三種顏色再進行額外編碼。

在路徑問題中我們的輪廓線是由 \(m\) 個上插頭與 \(1\) 個左插頭組成的。本題中，由於我們還需要判斷當前格點為右下角的 \(2\times 2\) 子矩形是否合法，所以需要記錄左上角格子的顏色，因此輪廓線的長度依然是 \(m+1\)。

這樣的編碼方案中依然保留了很多冗餘信息，（連通的區域顏色一定相同，且左上角的格子只需要顏色信息不需要連通性），但是因為已經用了哈希表和最小表示，對時間複雜度的影響不大，為了降低編程壓力，就不再細化了。

在最多情況下（例如第一行黑白相間），每個插頭的連通性信息都不一樣，因此我們需要 \(4\) 位二進制位記錄連通性，再加上顏色信息，本題的 Offset 為 \(5\) 位。

代碼實現 
 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
const 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) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= Offset;
    s |= (bi << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  REP(i, m + 1) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

手寫哈希

因為需要構造任意一組方案，這裏的哈希表我們需要添加一組域 pre[] 來記錄每個狀態在上一階段的任意一個前驅。

代碼實現 
 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
const 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() { REP(ii, sz) state[ii] <<= Offset; }
};

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

方案構造

有了上面的信息，我們就可以容易的構造方案了。首先遍歷當前哈希表中的狀態，如果連通塊數目不超過 \(2\)，那麼統計進方案數。如果方案數不為 \(0\)，我們倒序用 pre 數組構造出方案，注意每一行的末尾因為我們執行了 Roll() 操作，顏色需要取 c[j+1]。

代碼實現 
 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
void print() {
  T_key z = 0;
  int u;
  REP(i, H1->sz) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    DWN(i, n, 0) {
      B[i][m] = 0;
      DWN(j, m, 0) {
        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];
      }
    }
    REP(i, n) puts(B[i]);
  }
  puts("");
}

狀態轉移

我們記：

  • cc 當前正在染色的格子的顏色
  • lf 左邊格子的顏色
  • up 上邊格子的顏色
  • lu 左上格子的顏色

我們用 \(-1\) 表示顏色不存在。接下來討論狀態轉移，一共有三種情況，合併，繼承與生成：

狀態轉移 - 代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    REP(i, m + 1) 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);
}

對於最後一種情況需要注意的是，如果已經生成了一個封閉的連通區域，那麼我們不能再使用她的顏色染色，否則這種顏色會出現兩個連通塊。我們似乎需要額度記錄這種事件，可以參考 「ZOJ 3213」Beautiful Meadow 中的做法，再開一維記錄這個事件。不過利用本題的特殊性，我們也可以特判掉。

特判 - 代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
  REP(i, m + 1) 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;
}

進一步討論連通塊消失的情況。每當我們對一個格子進行染色後，如果沒有其他格子與其上側的格子連通，那麼會形成一個封閉的連通塊。這個事件僅在最後一行的最後兩列時可以發生，否則後續為了不出現 \(2\times 2\) 的同色連通塊，這個顏色一定會再次出現，除了下面的情況：

1
2
3
2 2
o#
#o

我們特判掉這種情況，這樣在本題中，就可以偷懶不用記錄之前是否已經生成了封閉的連通塊了。

例題代碼 
  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
#include <bits/stdc++.h>
using namespace std;
typedef long long T_state;
typedef int T_key;
const int N = 8;
int n, m;
char A[N + 1][N + 1], B[N + 1][N + 1];
const 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;
  }
}

const 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++) scanf("%s", 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++) puts(B[i]);
  }
  puts("");
}

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

習題

習題 「Topcoder SRM 312. Div1 Hard」CheapestIsland

題目大意：給一個棋盤圖，每個格子有權值，求權值之和最小的連通塊。

習題 「JLOI 2009」神秘的生物

題目大意：給一個棋盤圖，每個格子有權值，求權值之和最大的連通塊。

習題 「AtCoder Beginner Contest 211. Problem E」Red Polyomino

題目大意：給一個 \(N\times N\) 大小的棋盤圖，每個格子初始為黑色或白色。你可以從白色格子中挑選恰好 \(K\) 個並將之染成紅色，問有多少種染色方案滿足紅色格子形成一個連通塊。

圖論模型

例題 「NOI 2007 Day2」生成樹計數

題目大意：某類特殊圖的生成樹計數，每個節點恰好與其前 \(k\) 個節點之間有邊相連。

例題 「2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E」Efficient Tree

題目大意：給出一個 \(N\times M\) 的網格圖，以及相鄰四連通格子之間的邊權。 對於一顆生成樹，每個節點的得分為 1+[有一條連向上的邊]+[有一條連向左的邊]。 生成樹的得分為所有節點的得分之積。

你需要求出：最小生成樹的邊權和，以及所有最小生成樹的得分之和。 （\(n\le 800,m\le 7\)）

實戰篇

例題

例題 「HDU 4113」Construct the Great Wall

題目大意：在 \(N\times M\) 的棋盤內構造一組迴路，分割所有的 x 和 o。

有一類插頭 DP 問題要求我們在棋盤上構造一組牆，以分割棋盤上的某些元素。不妨稱之為修牆問題，這類問題既可視作染色模型，也可視作路徑模型。

greatwall

在本題中，如果視作染色模型的話，不僅需要額外討論染色區域的周長，還要判斷在角上觸碰而導致不合法的情況（圖 2）。另外與 「UVa 10572」Black & White 不同的是，本題中要求圍牆為簡單多邊形，因而對於下面的回字形的情況，在本題中是不合法的。

1
2
3
4
3 3
ooo
oxo
ooo

因而我們使用路徑模型，轉化為 一條迴路 來處理。

我們沿着棋盤的交叉點進行 DP（因而長寬需要增加 \(1\)），每次轉移時，需要保證所有的 x 在迴路之外，o 在迴路之內。因此我們還需要維護當前位置是否在迴路內部。對於這個信息我們可以加維，也可以直接統計輪廓線上到這個位置之前出現下插頭次數的奇偶性（射線法）。

例題代碼 
  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
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; ++i)

template <class T>
bool checkMin(T &a, const T b) {
  return b < a ? a = b, 1 : 0;
}

const int N = 10, M = N;
const int offset = 3, mask = (1 << offset) - 1;
int n, m;
int d;
const int INF = 0x3f3f3f3f;
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;
  }
}

const 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) {
        checkMin(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;

char A[N + 1][M + 1];

void push(int i, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  if (A[i][j] != '.') {
    bool bad = A[i][j] == 'o';
    REP(jj, j + 1) if (b[jj]) bad ^= 1;
    if (bad) return;
  }
  H1->push(encode());
}

int solve() {
  cin >> n >> m;
  int ti, tj;
  REP(i, n) {
    scanf("%s", A[i]);
    REP(j, m) if (A[i][j] == 'o') ti = i, tj = j;
    A[i][m] = '.';
  }
  REP(j, m + 1) A[n][j] = '.';
  ++n, ++m, ++ti, ++tj;
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 0;
  H1->push(0);
  int z = INF;
  REP(i, n) {
    REP(j, m) {
      swap(H0, H1);
      H1->clear();
      REP(ii, H0->sz) {
        decode(H0->state[ii]);
        d = H0->key[ii] + 1;
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            int cnt = 0;
            REP(i, m + 1) if (b[i])++ cnt;
            if (cnt == 2 && i == ti && j == tj) {
              checkMin(z, d);
            }
          } else {
            REP(i, m + 1) if (b[i] == lt) b[i] = up;
            push(i, j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(i, j, t, 0);
          }
          if (rt) {
            push(i, j, 0, t);
          }
        } else {
          --d;
          push(i, j, 0, 0);
          ++d;
          if (dn && rt) {
            push(i, j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  if (z == INF) z = -1;
  return z;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
#endif
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    printf("Case #%d: %d\n", Case, solve());
  }
}

習題

習題 「SCOI 2011」地板

題目大意：\(r\times c\) 的棋盤上有一些位置設置障礙，問使用 L 型的瓷磚鋪滿所有沒有障礙的格子，有多少種方案。

習題 「HDU 4796」Winter's Coming

題目大意：在 \(N\times M\) 的棋盤內對未染色的格點進行黑白灰染色，要求所有黑色區域和白色區域連通，且黑色區域與白色區域分別與棋盤的上下邊界連通，且其中黑色區域與白色區域不能相鄰。每個格子有對應的代價，求一組染色方案，最小化灰色區域的代價。

4796

習題 「ZOJ 2125」Rocket Mania

題目大意：\(9\times6\) 的地圖上每個格子裏是一種管道（-,T,L,+ 型或沒有），可以把管道旋轉 0°,90°,180°,270°, 問地圖最多能有幾行的右邊界與第 X 行的左邊界通過管道相連。

習題 「ZOJ 2126」Rocket Mania Plus

題目大意：\(9\times6\) 的地圖上每個格子裏是一種管道（-,T,L,+ 型或沒有），可以把管道旋轉 0°,90°,180°,270°, 問地圖最多能有幾行的右邊界與左邊界通過管道相連。

習題 「World Finals 2009/2010 Harbin」Channel

題目大意：一張方格地圖上用 . 表示空地、# 表示石頭，找到最長的一條路徑滿足：

  1. 起點在左上角，終點在右下角。
  2. 不能經過石頭。
  3. 路徑自身不能在八連通的意義下成環。（即包括拐角處也不能接觸）
習題 「HDU 3958」Tower Defence

題目大意：可以轉化為求解一條從 \(\mathit{S}\) 到 \(\mathit{T}\) 的不能接觸的最長路徑，拐角處可以接觸。

習題 「UVa 10531」Maze Statistics

題目大意：有一個 \(N\times M\) 的圖，每個格子有獨立概率 \(\mathit{p}\) 變成障礙物。你要從迷宮左上角走到迷宮右下角。求每個格子成為一個 有解迷宮（即起點終點四聯通） 中的障礙物的概率。（\(N \le 5\)，\(M \le 6\)）

習題 「Aizu 2452」Pipeline Plans

題目大意：現有一共 12 種圖案的瓷磚，每種瓷磚數量給定。要求鋪到一塊可視為 \(R\times C\) 網格圖的矩形地板上，一個格子鋪一塊瓷磚，且左上角格子的中心與右下角格子的中心通過瓷磚圖案上的線聯通。\((2 \le R \times C \le 15)\)

plug2

習題 「SDOI 2014」電路板

題目大意：一塊 \(N\times M\) 的電路板，上面有些位置是電線不能走的障礙，給定 \(K\) 個格子對，要求每對格子都有電線相連，且電線之間互不相交（允許一條電路線從上邊界進入當前格子，從左邊界離開這個格子，另外一條電路線可以從下邊界進入格子，從右邊界出去）。視電線為無向邊，求滿足要求的最短電線長度和方案數。

習題 「SPOJ CAKE3」Delicious Cake

題目大意：一塊可視為 \(N\times M\) 網格的蛋糕，現沿着格線將蛋糕切成數塊，問有多少種不同的切割方法。切法相同當且僅當切成的每塊蛋糕都形狀相同且在同一位置上。（\(\min(N,M) \le 5, \max(N,M) \le 130\)）

本章註記

插頭 DP 問題通常編碼難度較大，討論複雜，因而屬於 OI/ACM 中相對較為 偏門的領域。這方面最為經典的資料，當屬 2008 年 陳丹琦 的集訓隊論文——基於連通性狀態壓縮的動態規劃問題。其次，HDU 的 notonlysuccess 2011 年曾經在博客中連續寫過兩篇由淺入深的專題，也是不可多得的好資料，不過現在需要在 Web Archive 裏考古。

多米諾骨牌覆蓋

「HDU 1400」Mondriaan’s Dream 也出現在 《算法競賽入門經典訓練指南》 中，並作為《輪廓線上的動態規劃》一節的例題。多米諾骨牌覆蓋（Domino tiling） 是一組非常經典的數學問題，稍微修改其數據範圍就可以得到不同難度，需要應用不同的算法解決的子問題。

當限定 \(m=2\) 時，多米諾骨牌覆蓋等價於斐波那契數列。《具體數學》 中使用了該問題以引出斐波那契數列，並使用了多種方法得到其解析解。

當 \(m\le 10,n\le 10^9\) 時，可以將轉移方程預處理成矩陣形式，並使用 矩陣乘法進行加速。

domino_v2_transform_matrix

當 \(n,m\le 100\)，可以用 FKT Algorithm 計算其所對應平面圖的完美匹配數。

一條路徑

「一條路徑」是 哈密頓路徑（Hamiltonian Path） 問題在 格點圖（Grid Graph） 中的一種特殊情況。哈密頓路徑的判定性問題是 NP-complete 家族中的重要成員。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用