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]);
}

碎碎念

值得慶賀的事，Ranking 進世界百大!!!! 我相信這是誤打誤撞XDDD，不過真的蠻爽的。 @2008.11.10