Skip to content

DP on DAG

Definition

A DAG (Directed Acyclic Graph) is a directed acyclic graph. Many practical binary relations can be modeled using DAGs, thereby transforming these problems into longest (or shortest) path problems on DAGs.

Explanation

Let's use this problem as an example to analyze the process of DAG modeling.

Example Problem UVa 437 The Tower of Babylon

There are \(n (n\leqslant 30)\) types of bricks, each with known three side lengths, and each type has an infinite supply. The goal is to select some bricks to stack into a tower as high as possible (each brick can choose any of its edges as its height), such that the length and width of the bottom face of each brick are strictly smaller than those of the brick below it. Find the maximum possible height of the tower.

Process

Constructing the DAG

Since the length and width of the bottom face of each brick must be strictly smaller than those of the brick below it, it is natural to use this relationship as the basis for building the graph. Thus, the problem is transformed into a longest path problem.

That is, if brick \(j\) can be placed on brick \(i\), then there exists an edge \((i, j)\) between \(i\) and \(j\), and the edge weight is the height chosen for brick \(j\).

Another issue in this problem is that each brick has three possible choices for its height. How should we construct the graph more appropriately?

We can decompose each brick into three stacking methods, i.e., split one brick into three bricks, each corresponding to a different chosen height.

The initial starting point is the ground. The ground's bottom face is infinitely large, so the ground can reach any brick. Of course, we don't need to explicitly write infinity in our program.

Suppose there are two bricks with side lengths \(31, 41, 59\) and \(33, 83, 27\), respectively. Then the entire DAG should look like the figure below.

The blue solid boxes in the figure represent a set of bricks obtained by decomposing one brick. The \(\{\}\) notation is used for the bottom face dimensions because once a brick's height is chosen, the order of the bottom face length and width becomes irrelevant.

The yellow dashed boxes in the figure represent repeated calculations, which can be avoided using memoization search.

Transition

The problem asks for the maximum height of the tower, which has been transformed into a longest path problem. The starting point, as mentioned above, is the ground. What about the ending point? Clearly, the ending point is naturally determined: when no more bricks can be placed on top of a brick.

Now let's consider the transition equation.

Let \(d(i,r)\) denote the maximum height when the \(i\)-th brick is at the bottom and the \(r\)-th stacking method is used. Then the transition equation is as follows:

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

Here, \(j\) refers to all bricks that can be placed on brick \(i\) when it is stacked using method \(r\), \(r'\) corresponds to the stacking method of \(j\) at that time, and \(h\) is the height of brick \(i\) when using the \(r\)-th stacking method.

Implementation 
 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;
constexpr int MAXN = 30 + 5;
constexpr int 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) {  // Handle three directions
    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++) {  // Call different recursions based on different conditions
    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++) {  // Three construction methods
    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) {  // Infinite loop to find answers
    int n;
    cin >> n;
    if (n == 0) break;  // Stop if no bricks
    t++;
    for (int i = 0; i < n; i++) {
      cin >> x[i] >> y[i] >> z[i];
    }
    cout << "Case " << t << ":"
         << " maximum height = " << babylon(n);  // Recursion
    cout << endl;
  }
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用