a349. P-6-15. 一覽衆山小 - 彰化精誠中學

內容

所謂「會當凌絕頂，一覽衆山小。」很多人都想爬到高處，為的是將群山看小，但是登高必自卑，行遠必自邇，最好是一步一步逐步往上，妄想一步登天的人往往摔的慘重。小說與遊戲中出現的人物往往都是越晚出現越厲害，現在已知所有人物的戰力與出場順序，想要找出依照出場順序而且戰力逐步上升的人物序列，請你計算滿足這樣要求的序列的最大可能長度。

輸入說明

第一行有一個正整數 n 代表出場的人物數。第二行有 n 個非負整數是依
出場順序的每一位人物的戰力，數字間以空白隔開。 n  2e5，戰力值不超過1e8。

輸出說明

出場順序與戰力皆遞增的序列的最大可能長度。

範例輸入 #1

8
2 4 1 3 6 4 6 9

範例輸出 #1

範例輸入 #2

5
5 4 3 2 1

範例輸出 #2

測資資訊：

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

提示：

範例一說明：可以挑選子序列(1,3,4,6,9)，長度為5。
範例二說明：輸入是個遞減序列，找不到長度大於1的遞增子序列。

標籤:

出處:

AP325 [管理者：

haha (大學長)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」