d052. 11456 - Trainsorting
標籤 : DP LIS 最長遞增子序列
通過比率 : 443人/735人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2008-11-14 15:49

內容

艾琳是個開火車的機師,她也負責車廂的調度。她喜歡把車廂依重量由大到小排列,把最重的車廂擺在火車的前方。

不幸的是,排列車廂並不容易。你不能直接把一截車廂拿起來放在別處。把一截車箱插入現有的列車中間並不切實際。一截車廂僅能接在列車的前面或後面。

車廂以事先排定的順序抵達車站。當一截車廂抵達時,艾琳可以把它接在列車的前方或後方,或根本不要這截車廂。列車越長越好,但是其中的車廂要依重量排列。

依車廂抵達的順序給你車廂的重量,艾琳所能接出的最長火車是多長?

輸入說明

第一行的數字表示以下有幾筆測試資料,每筆測試資料的格式如下:

第一行有一個整數0 <= n <= 2000,表示車箱數。接下來的 n 行每行有一個非負整數表示車廂的重量。每個車廂的重量均不同。

輸出說明

輸出一個整數表示依所給限制所以接出最長火車的車廂數。

範例輸入 #1
1
3
1
2
3
範例輸出 #1
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
LIS
標籤:
DP LIS 最長遞增子序列
出處:
UVa11456 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

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