UVA437巴比伦塔
题目
巴比伦人有n种长方形方块,每种有无限个,第i种方块的三边边长是xi,yi,zi。对于每一个方块,你可以任意选择一面作为底,这样高就随着确定了。举个例子,同一种方块,可能其中一个是竖着放的,一个是侧着放的,一个是横着放的。
他们想要用堆方块的方式建尽可能高的塔。问题是,只有一个方块的底的两条边严格小于另一个方块的底的两条边,这个方块才能堆在另一个上面。这意味着,一个方块甚至不能堆在一个底的尺寸与它一样的方块的上面。
解题思路
- 对于每种长方体,总共有三种摆放方式
- 尺寸相同且摆放方式相同的长方体最多使用一次。
解法一:DP
状态转移方程:$dp[i]=dp[j]+a[i].h$
AC代码:
1 |
|
解法二:建图最长路
最长路可以用SPFA求,时间复杂度为$O(VE)$,也可以用拓扑排序+DP求时间复杂度为$O(N)$
SPFA代码:
1 |
|
拓扑排序+DP代码:
1 |
|