d242: 00481 - What Goes Up
Tags : DP LIS 最長遞增子序列
Accepted rate : 351人/445人 ( 79% ) [非即時]
評分方式:
Strictly

最近更新 : 2015-08-28 14:54

Content

Q481: What Goes Up

寫一個程式從一連串的整數序列中選出最長的嚴格遞增子序列(strictly increasing subsequence)。例如:在 1, 3, 2, 2, 4, 0 中最長的嚴格遞增子序列為 1,3, 4 或者 1, 2, 4。

Input

只有一組測試資料。

輸入包含一連串的整數(大約500000個),每個整數一列。請參考Sample Input。

Output

首先輸出一列最長的嚴格遞增子序列的長度是多少。然後一列僅含有一個減號(dash character, '-')。然後接下來為這個最長的嚴格遞增子序列的內容,每個整數一列。

如果有不止一個最長的嚴格遞增子序列,請輸出在輸入中最後出現的。例如在 1, 3, 2, 2, 4, 0 中,應該輸出 1, 2, 4 而不是 1, 3, 4。

請參考Sample Output。

Sample Input #1
-7
10
9
2
3
8
8
1


Sample Output #1
4
-
-7
2
3
8

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (25%): 1.0s , <1M
公開 測資點#1 (25%): 1.0s , <1M
公開 測資點#2 (25%): 1.0s , <1M
公開 測資點#3 (25%): 1.0s , <10M
Hint :
Tags:
DP LIS 最長遞增子序列
出處:
UVa481 [管理者: nanj0178(nanj) ]


ID User Problem Subject Hit Post Date
31520 a302854888@g...(小麥) d242
DP 兼 二分搜
105 2022-08-05 20:49
25829 allllllan123...(God of Computer...) d242
598 2021-06-25 21:53
24119 fire5386(Penguin07) d242
binary search O(nlogn)
910 2021-01-20 18:31