uva 437 The Tower of Babylon(DAG最长路）
题目连接：437 - The Tower of Babylon
题目大意：可以理解成有n种类型的长方体，现在给出每中长方体的长宽高， 然后要选取若干个长方体来玩堆积木（可以选取同种类型的长方体）， 要尽量使得堆出来的塔越高， 堆积木的时候要求下面的积木长宽一定要分别大于上面的那个积木（这样同种积木也有可能叠加）。
解题思路：DAG最长路径， 因为下面一个的长方体的长宽要分别大于上面一个长方体的长宽，所以为了不出先环状的结构，让一种长方体分解成三个长方体。让后用普通的最长路径去做。
#include <stdio.h>#include <string.h>const int N = 100005;struct state { int r; int c; int h;}tmp[N];int n, dp[N];void build(int k) { int a, b, c; scanf("%d%d%d", &a, &b, &c); k *= 3; tmp[k].r = a, tmp[k].c = b, tmp[k++].h = c; tmp[k].r = b, tmp[k].c = c, tmp[k++].h = a; tmp[k].r = c, tmp[k].c = a, tmp[k++].h = b;}int search(int k) { if (dp[k])return dp[k]; for (int i = 0; i < n; i++) {if ((tmp[k].r > tmp[i].r && tmp[k].c > tmp[i].c) || (tmp[k].r > tmp[i].c && tmp[k].c > tmp[i].r)) { if (dp[k] < search(i))dp[k] = search(i);} } return dp[k] += tmp[k].h;}int solve() { n *= 3; int Max = 0; for (int i = 0; i < n; i++) {if (!dp[i]) search(i);if (Max < dp[i]) Max = dp[i]; } return Max;}int main() { int cas = 1; while (scanf("%d", &n) == 1 && n) {// Init;memset(tmp, 0, sizeof(tmp));memset(dp, 0, sizeof(dp));// Read;for (int i = 0; i < n; i++) build(i);printf("Case %d: maximum height = %d\n", cas++, solve()); } return 0;}