k217. 11240 - Antimonotonicity - 高中生程式解題系統

回『UVa 題庫』

k217. 11240 - Antimonotonicity

標籤 :
通過比率 : 82人/92人 ( 89% ) [非即時]
評分方式：

Tolerant

最近更新 : 2023-03-27 11:02

內容

我有一個長度為 n 的 Fred 序列，由 1 到 n 之間的整數組成。Fred 序列的元素皆不相同。

我想找到一個盡可能長的 Fred 的子序列 Mary 並具有以下屬性：

Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...

輸入說明

第一行包含一個整數 T (T <= 50)

接下來 T 行，每行的一個數字為 n (n <= 30000)，代表接下來有 n 個數字

接下來 n 個數字，代表一個 Fred 序列

輸出說明

對於每個 Fred 序列，輸出最長子序列 Mary 的長度

範例輸入 #1

4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5

範例輸出 #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (50%): 1.0s , <1M

提示：

標籤:

出處:

UVA [管理者： ig99lp33lp33 (위즈원) ]

本題狀況本題討論排行