a484. CPE：Building designing (UVa 11039)

題目描述

有 n 個可選用的樓層，每層有一個大小與一種顏色。請從中選出若干層並排列，組成層數最多的建築。

排列必須符合：

• 每一層的大小，必須嚴格大於它正上方那一層的大小。
• 相鄰兩層的顏色必須不同。

所有可用樓層的大小彼此不同。每個樓層最多使用一次，不必全部使用，也不必保留輸入順序。

輸入格式

第一行為測試資料筆數 p。

每筆資料第一行為可用樓層數 n，n ≤ 500000。接下來 n 行，每行一個整數 x，−999999 ≤ x ≤ 999999，且 x ≠ 0。

x 為負數表示紅色樓層，正數表示藍色樓層；|x| 表示樓層大小。同一筆資料中不會有兩個樓層具有相同的絕對值。

輸出格式

每筆資料輸出一行，包含符合條件的建築最多能有多少層。

題目來源：2026/03/24 CPE 第 5 題，UVa 11039 — Building designing。 原題：https://cpe.mcu.edu.tw/cpe/problems/CPE260324/CPE260324-P5.uva11039.pdf