UVA - 437（DAG模型）

本文主要是介绍UVA - 437（DAG模型），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个盒子的高有三种状态，只要比较长和宽就行了。n个正方体可以看成n×3个矩形嵌套问题。可以转化成有向无环图，建完图后用记忆化搜索即可。

状态转移方程：d(i) = max{d(j) + box[i].z}

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 30 * 3 + 10;struct Box {int x;int y;int z;
} box[maxn];int d[maxn];
bool G[maxn][maxn];
int n;int dp(int i) {int& ans = d[i];if (ans > 0) return ans;ans = box[i].z;for(int j = 1; j <= 3*n; j++) {if (G[i][j]) ans = max(ans, dp(j) + box[i].z);}return ans;
}bool judge(Box a, Box b) {    // 判断a能否连到breturn (a.x > b.x && a.y > b.y || a.x > b.y && a.y > b.x);
}int main() {int kase = 0;freopen("input.txt", "r", stdin);while(~scanf("%d", &n) && n) {memset(G, false, sizeof(G));memset(d, -1, sizeof(d));for(int i = 1; i < 3 * n; i += 3) {scanf("%d%d%d", &box[i].x, &box[i].y, &box[i].z);box[i+1].x = box[i].z;box[i+1].y = box[i].x;box[i+1].z = box[i].y;box[i+2].x = box[i].y;box[i+2].y = box[i].z;box[i+2].z = box[i].x;}for(int i = 1; i <= 3 * n; i++) {for(int j = 1; j <= 3 * n; j++) {if (i == j) continue;else {if (judge(box[i], box[j])) {G[i][j] = true;}}}}int ans = -0x7fffffff;for(int i = 1; i <= 3 * n; i++) {ans = max(ans, dp(i));}printf("Case %d: maximum height = %d\n", ++kase, ans);}return 0;
}

这篇关于UVA - 437（DAG模型）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---