跳转至

DAG 上的 DP

定義

DAG 即 有向無環圖，一些實際問題中的二元關係都可使用 DAG 來建模，從而將這些問題轉化為 DAG 上的最長（短）路問題。

解釋

以這道題為例子，來分析一下 DAG 建模的過程。

例題 UVa 437 巴比倫塔 The Tower of Babylon

有 \(n (n\leqslant 30)\) 種磚塊，已知三條邊長，每種都有無窮多個。要求選一些立方體摞成一根儘量高的柱子（每個磚塊可以自行選擇一條邊作為高），使得每個磚塊的底面長寬分別嚴格小於它下方磚塊的底面長寬，求塔的最大高度。

過程

建立 DAG

由於每個磚塊的底面長寬分別嚴格小於它下方磚塊的底面長寬，因此不難將這樣一種關係作為建圖的依據，而本題也就轉化為最長路問題。

也就是説如果磚塊 \(j\) 能放在磚塊 \(i\) 上，那麼 \(i\) 和 \(j\) 之間存在一條邊 \((i, j)\)，且邊權就是磚塊 \(j\) 所選取的高。

本題的另一個問題在於每個磚塊的高有三種選法，怎樣建圖更合適呢？

不妨將每個磚塊拆解為三種堆疊方式，即將一個磚塊分解為三個磚塊，每一個拆解得到的磚塊都選取不同的高。

初始的起點是大地，大地的底面是無窮大的，則大地可達任意磚塊，當然我們寫程序時不必特意寫上無窮大。

假設有兩個磚塊，三條邊分別為 \(31, 41, 59\) 和 \(33, 83, 27\)，那麼整張 DAG 應該如下圖所示。

圖中藍色實線框所表示的是一個磚塊拆解得到的一組磚塊，之所以用 \(\{\}\) 表示底面邊長，是因為磚塊一旦選取了高，底面邊長就是無序的。

圖中黃色虛線框表示的是重複計算部分，可以採用 記憶化搜索 的方法來避免重複計算。

轉移

題目要求的是塔的最大高度，已經轉化為最長路問題，其起點上文已指出是大地，那麼終點呢？顯然終點已經自然確定，那就是某磚塊上不能再搭別的磚塊的時候。

下面我們開始考慮轉移方程。

設 \(d(i,r)\) 表示第 \(i\) 塊磚塊在最上面，且採取第 \(r\) 種堆疊方式時的最大高度。那麼有如下轉移方程：

\[ d(i, r) = \max\left\{d(j, r') + h\right\} \]

其中 \(j\) 是所有那些在磚塊 \(i\) 以 \(r\) 方式堆疊時可放上的磚塊，\(r'\) 對應 \(j\) 此時的擺放方式，\(h\) 對應磚塊 \(i\) 採用第 \(r\) 種堆疊方式時的高度。

實現 
 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
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN (30 + 5)
#define MAXV (500 + 5)
int d[MAXN][3];
int x[MAXN], y[MAXN], z[MAXN];

int babylon_sub(int c, int rot, int n) {
  if (d[c][rot] != -1) {
    return d[c][rot];
  }
  d[c][rot] = 0;
  int base1, base2;
  if (rot == 0) {  // 处理三个方向
    base1 = x[c];
    base2 = y[c];
  }
  if (rot == 1) {
    base1 = y[c];
    base2 = z[c];
  }
  if (rot == 2) {
    base1 = x[c];
    base2 = z[c];
  }
  for (int i = 0; i < n; i++) {  // 根据不同条件，分别调用不同的递归
    if ((x[i] < base1 && y[i] < base2) || (y[i] < base1 && x[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 0, n) + z[i]);
    if ((y[i] < base1 && z[i] < base2) || (z[i] < base1 && y[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 1, n) + x[i]);
    if ((x[i] < base1 && z[i] < base2) || (z[i] < base1 && x[i] < base2))
      d[c][rot] = max(d[c][rot], babylon_sub(i, 2, n) + y[i]);
  }
  return d[c][rot];
}

int babylon(int n) {
  for (int i = 0; i < n; i++) {
    d[i][0] = -1;
    d[i][1] = -1;
    d[i][2] = -1;
  }
  int r = 0;
  for (int i = 0; i < n; i++) {  // 三种建法
    r = max(r, babylon_sub(i, 0, n) + z[i]);
    r = max(r, babylon_sub(i, 1, n) + x[i]);
    r = max(r, babylon_sub(i, 2, n) + y[i]);
  }
  return r;
}

int main() {
  int t = 0;
  while (true) {  // 死循环求答案
    int n;
    cin >> n;
    if (n == 0) break;  // 没有砖头了就停止
    t++;
    for (int i = 0; i < n; i++) {
      cin >> x[i] >> y[i] >> z[i];
    }
    cout << "Case " << t << ":"
         << " maximum height = " << babylon(n);  // 递归
    cout << endl;
  }
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用