UVA437 The Tower of Babylon

UVA437 The Tower of Babylon

题目链接

动态规划

题目

有n(n≤30)种立方体，每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子(可以自行选择哪一条边作为高)，使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。

分析

题目中有两句话比较重要，一是每种立方体都有无穷多个，二是可以自行选择哪一条边作为高，所以当输入为n种立方体时，可供我们选择的立方体个数一共是3*n个，每输入一种立方体，对应的就有三种立方体供我们选择（分别以输入的三个数作为高）。 然后根据立方体之间能否摞在一起的关系可以建立有向无环图（DAG），利用邻接矩阵存储。 最后直接dp，用dp[i]存储从第i个立方体开始最高的高度，最后遍历取得最大值即可。

AC代码

#include
#include
#include
using namespace std;
const int MAX = 1000;
int n;
struct rec
{
	int a, b, h;
	rec(int x = 0, int y = 0, int z = 0)
	{
		a = x;
		b = y;
		h = z;
	}
};
rec recs[200];
int t1, t2, t3;
int G[200][200];
bool judge(rec x, rec y)//x能否放在y上面
{
	if ((x.a > t3;
			recs[3 * i].a = t1;
			recs[3 * i].b = t2;
			recs[3 * i].h = t3;

			recs[3 * i + 1].a = t2;
			recs[3 * i + 1].b = t3;
			recs[3 * i + 1].h = t1;

			recs[3 * i + 2].a = t3;
			recs[3 * i + 2].b = t1;
			recs[3 * i + 2].h = t2;
		}
		graph();
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		for (int t = 0; t