UVa437 The Tower of Babylon

好久不見！

連結：Uva437 The Tower of Babylon

題目：

給你很多種磚塊的長、寬、高，請你蓋出一座盡量高的塔。
每種提供無限多個，你可以以任意面朝下去蓋這座塔。

一個磚塊可以蓋上另一個條件為：底部的邊長必須分別小於下面那塊的長與寬。
例如長寬 (4,3) 的磚塊可以蓋在 (4,5) 之上，而 (4,6) 與 (5,6) 不可。

做法：

一種磚塊有三種不同的高，所以一開始就把他們分成三種儲存。

將所有磚塊兩兩比對，若A可以蓋在B上，就連一條有向邊，磚塊的高即為該節點的權重。

於是就形成了一張DAG，然後從入度為零的地方開始DFS，找到最長路徑就是答案了。

這是我當下寫的方法，有另一個方法是將磚塊排序後找LIS即為答案。

code: