創作內容

0 GP

ZeroJudge - d052: 11456 - Trainsorting 解題心得

作者:Not In My Back Yard│2019-05-19 18:25:18│贊助:0│人氣:21
題目連結:


題目大意:
第一列給定一正整數,代表有幾組測試資料。每組測資第一列給定一正整數 n (0 ≦ n ≦ 2, 000),代表有 n 節車廂。

接下來有 n 列輸入,每列給定一非負整數,代表其中一節車廂的重量(每節車廂重量均不同)。

當每有一節車廂抵達車站(以輸入的順序),艾琳可以把它接在現有列車的前方或後方,或是乾脆不要接上列車。使得列車的每節車廂依重量排列。請問,列車最長可以有幾節車廂。



範例輸入:
1
3
1
2
3


範例輸出:
3


解題思維:
本題即是求最長遞增子序列(Longest Increasing Subsequence,LIS),例:5 7 2 3 8 的 LIS 為 5 7 8 。

而因為一節車廂可以接在現有的列車前面或後面。雖然表面上每次都有兩種選擇,但是只要選了某一邊開始接,之後的車廂必定也接在同一側(畢竟要保持重量的順序)。因此不只要求給定數列的 LIS ,也要求反序的數列之 LIS 。

雖然 LIS 有動態規劃(DP)的解法,但是時間複雜度為 O(n ^ 2)。而我們可以採取貪心演算法(Greedy Algorithm)的精神去得出 LIS 的長度:

每當有一新數字進來之後,判斷此數有無比現在 LIS 結尾的數值大。

如果此數大於 LIS 的結尾,那就直接放到 LIS 結尾的後面,成為新的結尾。
反之,此數小於結尾,則用二分搜尋法(Binary Search)去找到在 LIS 由左數來第一個大於此數的數字,並將其替代掉。(因為此數較小,所以「可能」可以接得更長)

當所有數字都依序檢查過後,即可得出 LIS 的長度。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4397896
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|貪婪演算法(Greedy algorithm)|最長遞增子序列(LIS)

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

justarabbit今天生日的你
生日快樂!你知道你的生日花語是什麼呢?來我的小屋看看吧~看更多我要大聲說昨天21:59


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】