UVA 437 The Tower of Babylon——dp

UVA 437 The Tower of Babylon——dp

建n*3个节点的DAG记忆化搜索一下就可以了，水题

#include #include #include #include using namespace std;const int maxn = 100;int kase = 1, n, G[maxn][maxn];struct Date { int x, y, z; } date[maxn];bool vis[maxn];int dp[maxn];int dfs(int u) { if (vis[u]) return dp[u]; vis[u] = true; int ans = 0; for (int i = 0; i < n*3; i++) { if (G[u][i]) { ans = max(ans, dfs(i)); } } ans += date[u].z; return dp[u] = ans;}int solve() { memset(G, 0, sizeof(G)); for (int i = 0; i < n*3; i++) { for (int j = 0; j < n*3; j++) { if (date[i].x > date[j].x && date[i].y > date[j].y) G[i][j] = 1; } } memset(vis, false, sizeof(vis)); for (int i = 0; i < n*3; i++) dfs(i); int ans = 0; for (int i = 0; i < n*3; i++) ans = max(ans, dp[i]); return ans;}int main() { while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) { int x, y, z; scanf("%d %d %d", &x, &y, &z); date[i*3].x = x, date[i*3].y = y, date[i*3].z = z; if (date[i*3].x < date[i*3].y) swap(date[i*3].x, date[i*3].y); date[i*3+1].x = x, date[i*3+1].y = z, date[i*3+1].z = y; if (date[i*3+1].x < date[i*3+1].y) swap(date[i*3+1].x, date[i*3+1].y); date[i*3+2].x = y, date[i*3+2].y = z, date[i*3+2].z = x; if (date[i*3+2].x < date[i*3+2].y) swap(date[i*3+2].x, date[i*3+2].y); } printf("Case %d: maximum height = %d\n", kase++, solve()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。