POJ 2241 The Tower of Babylon

题目地址:

题意:

给定N中方块，给定他们的长宽高，然后每一种方块的个数都为无限个。将任意数目的方块叠起来（但是要满足叠在一起的方块中，上面的方块的长和宽必须都小于下面方块的长和宽），问这些方块最多能叠多高。

思路:

DP求解。对Blocks的先按照X降级，再按照Y降级排序，可转化为最长公共子序列问题，即求子序列权值之和最大。可化为图算法，较笨。