UVa 103 Stacking Boxes
題目講解
這題給你一堆多維的箱子,要找出最長的裝箱序列,這個最常裝箱序列就是像俄羅斯娃娃那樣,大箱子裡面放入小箱子,一層包一層,必須要可以裝最多層這樣。這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ,不過這兒我們先不管 ),比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ,B箱比較大,所以 BoxA 可以裝進 BoxB 裡,那麼我們說 BoxA < BoxB 。
但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ,也不能說 BoxC > BoxD,BoxC 與 BoxD 兩者之間就沒有大小關係。
一個簡單的表示法就是有向圖(Directed Graph)
比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法:
到此為止,本題的最長裝箱序列,已經有兩種解法,第一個方法就是找圖的最長路徑,稍微修改 Warsahll algorithm 來解,第二個方法是跑 LIS 。
我這裡用 LIS(最長上昇子串列) 解法。
//先定義一個box struct struct Box { int no; int edge[10]; }; Box box[30];
LIS 法的關鍵是要先對箱子排序,確保小箱子一定在大箱子前,至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序,以字串的角度是字典排序,兩者都行。
sort(box[i].edge) for all i //先對箱子內部的邊長排序 int lexico_less(const Box& a, const Box& b) { for(int i=0;i<dimension;++i) if( !(a.edge[i]<=b.edge[i]) ) return false; return true; } sort(box) by lexico_less(); //再用字典序排箱子一切都準備好後,就可以直接套用LIS解了。
// LIS int length[MAX_BOX]; int prev[MAX_BOX]; length[i] = 1 for all i; prev[i] = -1 for all i; for(int i=0;i<num_box;++i) for(int j=i+1;j<num_box;++j) { if( box[i]<box[j] ) { if(length[i]+1 > length[j] ){ length[j] = length[i]+1; prev[j] = i; } } }輸出結果
int max = max_element(length, length+num_box) - length; //print the result printf("%d\n", length[max]); int output_seq[MAX_BOX]; int size = 0; int cur = max; do { output_seq[size++] = box[cur].no; cur = prev[cur]; } while( cur!= -1 ); for(int i=size-1;i>0;--i) printf("%d ", output_seq[i]); printf("%d\n", output_seq[0]); }
好像蠻多DP題都可以化成圖來做
回覆刪除不過這題我還是用LIS
不過時間複雜度很難算倒是真的
上網找解答的時候
才發現有人的寫法跟我一樣奇怪XDD
小弟正在寫acm 103題,但是卡了一陣子,實在想不到什麼好方法寫,是不是可以指點一下你解題的概念,雖然有程式碼,但是我對你使用的語言不很熟,謝謝
回覆刪除我想千言萬語不如一個好的方向
回覆刪除試著去搜尋 LIS算法(最長上升子序列)
這題的程式碼在下我自己都看得很心虛呀,寫得亂七八糟
其實這題不用DP
回覆刪除用greedy也可以AC
用greedy也能AC是因為測資薄弱,不夠有鑑別力,其實greedy作法是有缺陷的。
回覆刪除感謝題解~有向圖的思維沒想到
回覆刪除請問一下
int lexico_less(const Box& a, const Box& b)
這個排出來是照可不可以放入吧?
字典排序不是a.edge[i]<b.edge[i])