d052: 11456 - Trainsorting
Tags :
Accepted rate : 205人/332人 ( 62% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

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

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

Input

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

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

Output

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

Sample Input
1
3
1
2
3
Sample Output
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
LIS
Tags:
出處:
UVa11456 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」