POJ 2241 The Tower of Babylon

題目位址:

題意:

給定N中方塊，給定他們的長寬高，然後每一種方塊的個數都為無限個。将任意數目的方塊疊起來（但是要滿足疊在一起的方塊中，上面的方塊的長和寬必須都小于下面方塊的長和寬），問這些方塊最多能疊多高。

思路:

DP求解。對Blocks的先按照X降級，再按照Y降級排序，可轉化為最長公共子序列問題，即求子序列權值之和最大。可化為圖算法，較笨。