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

翻譯, UVa/ACM 本文总阅读量次

莫西亞 (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).
翻譯, UVa/ACM