POJ 2392 Space Elevator
題意：
有一些不同的磚塊，每個磚塊有一定的高度、數量、和最大高度限制，輸入第一列會給一個數字n，代表磚塊的種類，接下來n列會給每個磚塊的資訊，每列3個數字，(高度, 最大高度限制, 數量)，所謂最大高度限制是指，假設現在只有一種磚塊，資訊是2, 5, 100，2 + 2 + 2 > 5，雖然磚塊數量很多，但因為這種磚塊不能超過高度5，所以根據這些磚塊，我堆磚塊高度最高就只能到4，題目要求給定磚塊資訊下、各種磚塊滿足最大高度限制下，堆這些磚塊所能達到的最高高度是多少
解題思路：
多重背包問題(物品是有限的)，把高度想成背包重量上限，磚塊就是物品，現在物品的重量和價值的值一樣，比較不一樣的一點是，這個題目並沒給出一個有明確重量上限的背包要你去塞東西，而是求在滿足各種磚塊的最大高度限制下，所能堆出的磚塊堆最大高度是多少
很明顯的一點，堆出的最大高度 <= 所有磚塊裡的最大高度限制，因為不能超過磚塊的最大高度限制，所以我就想對於1 ~ n種磚塊，假設第i種磚塊的最大高度限制是max[i]、高度是h[i]，對於第i種磚塊，從背包重量上限max[i] ~ h[i]去考慮放或不放，整個流程做完，再從記錄狀態的DP陣列的末端開始往回找，找第一個DP[index] = index的就是了
可是結果TLE，後來改用以2為基底的數量湊堆的方式下去考慮，結果是錯的，這有點微妙，解釋起來有點麻煩，簡而言之，如果上述流程不是從最大高度限制最低的開始，依序增加的去考慮的話會錯...
有一些不同的磚塊，每個磚塊有一定的高度、數量、和最大高度限制，輸入第一列會給一個數字n，代表磚塊的種類，接下來n列會給每個磚塊的資訊，每列3個數字，(高度, 最大高度限制, 數量)，所謂最大高度限制是指，假設現在只有一種磚塊，資訊是2, 5, 100，2 + 2 + 2 > 5，雖然磚塊數量很多，但因為這種磚塊不能超過高度5，所以根據這些磚塊，我堆磚塊高度最高就只能到4，題目要求給定磚塊資訊下、各種磚塊滿足最大高度限制下，堆這些磚塊所能達到的最高高度是多少
解題思路：
多重背包問題(物品是有限的)，把高度想成背包重量上限，磚塊就是物品，現在物品的重量和價值的值一樣，比較不一樣的一點是，這個題目並沒給出一個有明確重量上限的背包要你去塞東西，而是求在滿足各種磚塊的最大高度限制下，所能堆出的磚塊堆最大高度是多少
很明顯的一點，堆出的最大高度 <= 所有磚塊裡的最大高度限制，因為不能超過磚塊的最大高度限制，所以我就想對於1 ~ n種磚塊，假設第i種磚塊的最大高度限制是max[i]、高度是h[i]，對於第i種磚塊，從背包重量上限max[i] ~ h[i]去考慮放或不放，整個流程做完，再從記錄狀態的DP陣列的末端開始往回找，找第一個DP[index] = index的就是了
可是結果TLE，後來改用以2為基底的數量湊堆的方式下去考慮，結果是錯的，這有點微妙，解釋起來有點麻煩，簡而言之，如果上述流程不是從最大高度限制最低的開始，依序增加的去考慮的話會錯...
Code：
留言
張貼留言