103 - Stacking Boxes

Sylveon

原題：http://luckycat.kshs.kh.edu.tw/homework/q103.htm
ACCODE：

非常麻煩的一題

qsort也非常難用

不過只要sort的地方做得好

後面做起來很輕鬆，lis就可以了

注意相等時並不能放入

簡單講一下想法好了

由於可以翻轉/扭曲（？）反正說穿了就是大對大、小對小

這種情形sort可以解決

不過用qsort的話，不論是二維或結構我都不會寫|||

後來只好先另開一維存，排完再丟進結構

之後就依每個盒子大小排序

排序的依據：小的放前面

提示：lis如果要做得順，就把最小的數字按小到大排序

若最小的數字相等，則後面數字由大到小排序

如此用我後面lis的方法才會順

lis的部份嘛

我是從頭開始找，若可以套入則略過（注意套入條件不包含相等）

若不能夠套入則把它蓋掉

原因：若不能夠套入這項，但前面的都能夠套入，故它該取代這項

然而為什麼可以直接取代是由於我把第一數字相等的情形

寫成依後面數字由大到小排序，如此直接覆蓋時

出現盒子之第一數字以非遞減順序呈現，故不列入考慮中

即後面出現的盒子在第一數字上可以蓋掉它

但相等的情形蓋不掉，不過因為後面是按大到小排序

因此在第一數字相同情形下，蓋到最後變成後面數字最小的留下

而後面比較第一數字時必可以蓋掉它，但它後面數字最小

故最可能可以套入後面的盒子，直接lis就可以順利完成

=========================================
Sylveon的補充

C++algorithm的sort可以有自訂比序函數的參數可用，操作較為簡單
=========================================
作者  zenixls2 (丁丁叮叮)                                  站內  sa072686
標題  [ACM] 103
時間  2007/12/06 Thu 11:33:04

0.000 in STL Map + C  Rank 40


對每一組輸入qsort，使其維度內為遞增排序

將其存於map，會自動捨去重複的(不過要重新定義運算子)，並作排序

再以LIS(n^2)作即可

鼓勵大家用STL+C寫code