a019: Stacking Boxes
標籤 :
通過比率 : 50% (5 人 / 10 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-04-03 10:20

內容 :

在數學或電腦科學裡,有些概念在一維或二維時還蠻簡單的,但到 N 維就會顯得非常複雜。試想一個 n 維的「盒子」:在二維空間裡,盒子 ( 2 , 3 ) 可代表一個長為 2 個單位,寬為 3 個單位的盒子;在三維空間裡,盒子 ( 4 , 8 , 9 ) 則是一個 4*8*9(長、寬、高)的盒子。至於在六維空間裡,也許我們不清楚 ( 4 , 5 , 6 , 7 , 8 , 9 ) 長得怎樣,不過我們還是可以分析這些盒子的特性。

在此問題裡,我們要算出一組 n 維盒子裡,它們的「最長套入串列」: b1, b2, ......,bk,其中每個盒子  bi 都可以「放入」盒子  bi+1 中(1 <= i < k)

考慮兩個盒子 D =( d1, d2, ......,dn ), E =( e1, e2, ......,en )。如果盒子 D 的 n 個維,能夠存在一種重排,使得重排後, D 每一維的量度都比 E 中相對應的維的量度還要小,則我們說盒子 D 能「放入」盒子 E 。(用比較不嚴謹的講法,這就好像我們將盒子 D 翻來翻去,看看能不能擺到 E 裡面去。不過因為我們考慮的是任一重排,所以實際上盒子不只可轉來轉去,甚至還可以扭曲。)(還是看看下面的例子說明好了)。

譬如說,盒子 D = ( 2 , 6 ) 能夠被放入盒子 E = ( 7 , 3 ) 裡,因為 D 可以重排變為 ( 6 , 2 ) ,這樣子 D 的每個維的量度都比 E 裡對應的維還要小。而盒子 D = ( 9 , 5 , 7 , 3 ) 就沒辦法放進盒子 E = ( 2 , 10 , 6 , 8 ) ,因為就算再怎摸重排 D 裡的維,還是沒辦法符合「放入」的條件。不過 F = ( 9 , 5 , 7 , 1 ) 就可以放入 E 了,因為 F 可以重排成 ( 1 , 9 , 5 , 7 ) ,這樣就符合了放入的條件。

我們今定義「放入」如下:對於任兩個盒子 D =( d1, d2, ......,dn)和 E =( e1, e2, ......,en ),如果存在一種 1..n 的重排π,使得對於任何的 1 <= i <= n,皆有 dπ(i) < ei,則我們說盒子 D 能「放入」盒子 E 。

輸入說明

輸入包含多組測試資料。每組測試資料的第一列有兩個數字:第一個是盒子的數量 k ,然後是盒子的維數 n 。

接下來有 k 列,每列有n個整數表示一個盒子的 n 個維的量度,量度之間由一個以上的空白做區隔。第一列表示第一個盒子,第二列表示第二個盒子,依此類推。

此問題裡,盒子的維數最小是 1 ,最大是 10 , 並且每組測試資料中盒子的個數最多為 30 個。

輸出說明

對於每一組測試資料,你必須輸出兩列數字:第一列是「最長套入串列」的長度,第二列是按照內外順序,印出「最長套入串列」裡盒子的編號(其中編號是按照在輸入檔案的每組數列裡所出現的順序,例如第一個盒子就是 1 號 . . . 等等。)最裡面的盒子(或是最小的)擺在第一個,再來是次小的,依此類推。

如果對於每一組的盒子,存在兩個以上的「最長套入串列」,輸出任何一個均可。

範例輸入
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
範例輸出
5
3 1 2 4 5
4
7 2 5 6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :

LIS, DP

標籤:
出處:
UVA [編輯: zero (管理員) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」