艾琳是個開火車的機師,她也負責車廂的調度。她喜歡把車廂依重量由大到小排列,把最重的車廂擺在火車的前方。
不幸的是,排列車廂並不容易。你不能直接把一截車廂拿起來放在別處。把一截車箱插入現有的列車中間並不切實際。一截車廂僅能接在列車的前面或後面。
車廂以事先排定的順序抵達車站。當一截車廂抵達時,艾琳可以把它接在列車的前方或後方,或根本不要這截車廂。列車越長越好,但是其中的車廂要依重量排列。
依車廂抵達的順序給你車廂的重量,艾琳所能接出的最長火車是多長?
第一行的數字表示以下有幾筆測試資料,每筆測試資料的格式如下:
第一行有一個整數0 <= n <= 2000,表示車箱數。接下來的 n 行每行有一個非負整數表示車廂的重量。每個車廂的重量均不同。
輸出一個整數表示依所給限制所以接出最長火車的車廂數。
1 3 1 2 3
3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|