[翻譯][UVa][11790] Murcia's Skyline

莫西亞 (Murcia,西班牙東南部的城市) 的摩天大樓成長得非常快速。從 15 世紀起,巴洛克式的 Glorieta 大教堂的輪廓就映照在這地平線上,但現在,新的摩天大樓開始矗立在莫西亞的田野 (huerta) 中。

有些人認為如果眼睛從左往右依序掃過,你可以觀察到一個越來越高的天際線,但其他人不認為是這樣,他們認為是越來越低的。

當我們的眼從左至右掃過莫西亞的天際,我們可以看到N個建築物,每個建築物有它自己的寬與高,你必須觀察出這些建築物是遞增還是遞減的排列著。我們定義如果建築群的最長遞增子序列 (longest increasing subsequence, LIS) 不小於最長遞減子序列 (longest decreasing subsequence, LDS) ,我們就稱它為遞增排列;反之,則稱為遞減排列。而子序列 (subsequence) 為原本序列在相同順序下的子集合,建築群的子序列長度為子序列中所有建築的寬之和。

舉例來說,假設我們有六座建築,而它們的高分別為:10、100、50、30、80、10;寬依序是:50、10、10、15、20、10。這時我們可以得出一條包含 3 棟建築物的遞增序列 (註:高為 10、30、80 的建築物)而它的長度和為 85,與一列包含 1 座建築的遞減序列 (註:高為 10 的建築物) 而它的長度和為 50 (當然這裡有一列含 4 棟建築的遞減序列,然而它的長度為 45),所以在這組測試資料中,我們可以說它的天際線是遞增的,範例請參照下圖。

輸入

輸入的第一行代表接下來的測試組數。對於每組測資,第一行包括一個整數 N,代表地平線上有幾棟建築物,接著的兩行,每行有 N 個由空白分開的整數,第一行從左至右依序為每個建築物的高,第二行則為建築物之寬。

輸出

對於每組測資,請輸出一行。如果天際線為遞增排列,則輸出格式為:

Case i. Increasing (A). Decreasing (B).

如果天際線為遞減,則輸出格式為:

Case i. Decreasing (B). Increasing (A).

上述 i 代表輸出的第幾筆測資,A 代表 LIS 序列的長度和,B 則代表 LDS 序列的長度之和。

範例輸入

1
2
3
4
5
6
7
8
9
10
3
6
10 100 50 30 80 10
50 10 10 15 20 10
4
30 20 20 10
20 30 40 50
3
80 80 80
15 25 20

範例輸出

1
2
3
Case 1. Increasing (85). Decreasing (50).
Case 2. Decreasing (110). Increasing (50).
Case 3. Increasing (25). Decreasing (25).
,