Q481: What Goes Up

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

輸入說明

只有一組測試資料。

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

輸出說明

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

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

請參考Sample Output。

範例輸入 #1

範例輸出 #1

測資資訊：

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

提示：

標籤:

DP LIS 最長遞增子序列

出處:

UVa 481 [管理者： nanj0178 (nanj) ]

本題狀況本題討論排行