UVa 437 The Tower of Babylon：DP&DAG

UVa 437 The Tower of Babylon：DP&DAG2014-07-28 csdn博客 synapse7

437 - The Tower of Babylon

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=378

思路：

对于一个（x,y,z）砖头，它可以有3中姿势放置：（前两个为地面，后一个为高）

x, y, z

x, z, y

y, z, x

把每种姿势都记录下来，变成了有3*n种固定姿势的砖头。

然后建图，求dag上的最长路。

完整代码：

/*0.015s*/#include<bits/stdc++.h>using namespace std;int a[100][3], dp[100], n;int DAG（int x）{if （dp[x] ！= -1） return dp[x];dp[x] = a[x][2];///高for （int y = 0; y < n; ++y）{if （y == x） continue;if （a[y][0] < a[x][0] && a[y][1] < a[x][1] && dp[x] < DAG（y） + a[x][2]）dp[x] = DAG（y） + a[x][2];}return dp[x];}int main（）{int cas = 0, maxh, i;while （scanf（"%d", &n） , n）{n += n << 1;memset（dp, -1, sizeof（dp））;for （i = 0; i < n; i += 3）{scanf（"%d%d%d", &a[i][0], &a[i][1], &a[i][2]）;sort（a[i], a[i] + 3）;a[i + 1][0] = a[i][0], a[i + 1][1] = a[i][2], a[i + 1][2] = a[i][1];a[i + 2][0] = a[i][1], a[i + 2][1] = a[i][2], a[i + 2][2] = a[i][0];}maxh = 0;for （i = 0; i < n; ++i）if （maxh < DAG（i）） maxh = dp[i];printf（"Case %d: maximum height = %d
", ++cas, maxh）;}return 0;}