uva 437 The Tower of Babylon(DAG最长聊）

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;
}