DP on DAGs

Definition

A DAG is a directed acyclic graph. Binary relations in some practical problems can be modeled using DAGs, thereby transforming these problems into longest (shortest) path problems on DAGs.

Explanation

Let us use this problem as an example to analyze the process of modeling with a DAG.

Process

Building the DAG

Since the length and width of each block's base are strictly less than those of the block below it, it is not difficult to use this relation as the basis for building the graph, and this problem is thereby transformed into a longest-path problem.

In other words, if block $j$ can be placed on block $i$, then an edge $(i, j)$ exists between $i$ and $j$, and the edge weight is the height chosen for block $j$.

Another issue in this problem is that each block has three choices of height. How should we build the graph more appropriately?

We may split each block into three stacking configurations; that is, decompose one block into three blocks, with each resulting block choosing a different height.

The initial starting point is the ground. The ground has an infinitely large base, so it can reach any block; of course, when writing the program, we do not need to explicitly add infinity.

Suppose there are two blocks with side lengths $31, 41, 59$ and $33, 83, 27$, respectively. Then the entire DAG should look as follows.

The blue solid-line box in the figure represents a group of blocks decomposed from one block. The base side lengths are represented by $\{\}$ because once a block has selected its height, the base side lengths are unordered.

The yellow dashed-line box in the figure represents the part that is computed repeatedly. Memoized search can be used to avoid repeated computation.

Transitions

The problem asks for the maximum height of the tower, which has been transformed into a longest-path problem. As pointed out above, its starting point is the ground. What about the endpoint? Clearly, the endpoint is determined naturally: it is when no other block can be placed on a certain block.

Now we begin considering the transition equation.

Let $d(i,r)$ denote the maximum height when block $i$ is at the bottom and uses stacking configuration $r$. Then the following transition equation holds:

Here, $j$ ranges over all blocks that can be placed on block $i$ when it is stacked in configuration $r$, $r'$ corresponds to the placement configuration of $j$ at that time, and $h$ corresponds to the height when block $i$ uses stacking configuration $r$.

#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) {  // Process the 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 recursive functions according to 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 ways to build the graph
    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) {  // Use an infinite loop to find the answer
    int n;
    cin >> n;
    if (n == 0) break;  // Stop when there are no more blocks
    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;
}