链接：The Tower of Babylon 耗时：0.015s

这是刘汝佳的紫书中”DAG 中的动态规划”中的习题，我拿它用来熟悉 DAG 中的动态规划。

我们不妨进行逆向考虑：现堆上面的方块，然后考虑在下面进行叠加。这样子一来，影响决策的就只是最下面方块的尺寸了。

对于这种出现了”大套小”这样的二元关系的题，我们可以将其视为一个有向无环图：其中每个节点为一个状态，状态的转移是有固定的方向的（在此题中，状态转移为从小的方块到大的方块）。

但是这道题又不同于平常的 DAG 动态规划：若将边长视为状态的话，则要开一个巨大的数组，这是不可以接受的。因此，我们要换一种思维方式：只记录方块的序号和摆放的方式（如现将边长从小到大进行排序，然后用一个标志 k 表示当前是以第 k 小的边长作为高）。

至此，思路已经清晰了。用 $dp(i, k)$ 表示 “第 i 个方块以第 k 条边为高进行摆放” ，以下给出状态转移方程：

$$dp(i, k) = max\{dp(i, k), dp(j, k_2)\}$$

其中 $j，k_2$ 遍历所有顶面矩形比 $dp(i, k)$ 小的状态。

代码实现首次尝试了 Pascal 中的 object 类型，使其更加工整，但不可避免地损耗了一些性能。

type    Cube = object        a: array [1..3] of longint;        procedure init(x,y,z: longint);        function height(k: integer): longint;        function low(k: integer): longint;        function high(k: integer): longint;    end;function max(x,y: longint): longint;begin    if x>y then max := x else max := y;end;procedure swap(var x,y: longint);var    t: longint;begin    t := x;    x := y;    y := t;end;function Cube.height(k: integer): longint;begin    height := self.a[k];end;function Cube.high(k: integer): longint;begin    case k of        1: high := a[3];        2: high := a[3];        3: high := a[2];    end;end;function Cube.low(k: integer): longint;begin    case k of        1: low := a[2];        2,3: low := a[1];    end;end;procedure Cube.init(x, y, z: longint);begin   if x>y then swap(x,y);   if y>z then swap(y,z);   if x>y then swap(x,y);   a[1] := x;   a[2] := y;   a[3] := z;end;var    f: array [1..30, 1..3] of longint;    i,j,m,n,x,y,z: longint;    cnt: longint;    cubes: array [1..30] of Cube;function dp(id, k: integer): longint;var    l, h, hi: longint;    i, j: integer;begin    if f[id, k] > 0 then        exit(f[id, k]);    l := cubes[id].low(k);    hi := cubes[id].height(k);    h := cubes[id].high(k);    f[id, k] := hi;    for i := 1 to n do    begin        //if i = id then continue;  //此处在一开始时忘记考虑了立方体有无穷多个这一条件。        for j := 1 to 3 do        begin            if not ((cubes[i].low(j) < l) and (cubes[i].high(j) < h)) then                continue;            f[id, k] := max(f[id, k], dp(i, j)+hi);        end;    end;    dp := f[id, k];end;begin    assign(input, 'main.in');reset(input);    assign(output, 'main.out');rewrite(output);    read(n);    cnt := 0;    while n > 0 do    begin        inc(cnt);        for i := 1 to n do        begin            read(x,y,z);            cubes[i].init(x,y,z);        end;        fillchar(f, sizeof(f), 0);        m := 0;        for i := 1 to n do            for j := 1 to 3 do                m := max(m, dp(i, j));        writeln('Case ', cnt, ': maximum height = ', m);        read(n);    end;    close(input);close(output);end.