UVa 437 The Tower of Babylon (DPDAG)

本文主要是介绍UVa 437 The Tower of Babylon (DPDAG)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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\n", ++cas, maxh);}return 0;
}

这篇关于UVa 437 The Tower of Babylon (DPDAG)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---