Re: [問題] ACM Trainsorting
不好意思我懶得看他的說明了，直接照我理解的講一次。題目敘述是這樣的（複製的）：
把車廂依重量由大到小排列，車廂以事先排定的順序抵達車站。當一截車廂抵
達時，可以依重量把它接在列車的前方或後方或不要這截車廂。列車越長越
好，但車廂要依重量排列。最後算出接出的最長火車是多長？
假設最佳解的最佳序列是 a_1, a_2, ..., a_n，且設其中最早加入序列的車是 a_m，
那我們知道排在 a_m 以後的車子（如果有的話）a_{m+1}, a_{m+2}, ..., a_n 必定
都比 a_m 還晚加入（而且越後面越晚加入）
排在 a_m 以前的子（如果有） a_1, a_2, ..., a_{m-1} 也一定比 a_m 還晚加入序列
（這次是越前面的越晚加入。）
好，接下來看序列 a_m, a_{m+1}, a_{m+2}, ..., a_n，顯然它們最長的可能就是以 a_m
開頭的 LDS（要包含 a_m），對所有的 1≦m≦n 可以在總共 O(n lg n) 的時間求出
然後看序列 a_m, a_{m-1}, a_{m-2}, ..., a_1（就是 a_m 前面的序列翻轉過來，因為
這樣凸顯出加入順序），很明顯它也是以 a_m 開頭的 LIS（也要包含 a_m）。同樣，也
可以對所有 1≦m≦n 在總共 O(n lg n) 的時間內求出。
於是假若某個 a_m 在最佳解中的話，那最佳解長度就是 LIS(m)+LDS(m)-1。因為以 a_m
起頭的 LIS、LDS 絕對不會有重複的數字（除了a_m）。但我們並不知道哪個 a_m 在最佳
解當中，於是就枚舉 1≦m≦n，這樣總時間複雜度是 O(nlgn + nlgn + n) = O(n lg n)
至於為什麼要從尾巴算？因為你要求出的是「以每個a_m起頭的LIS、LDS」各是多少。從
頭算的話算出來的不是你要的東西。
※ 引述《k577887 (HaHa-Dog)》之銘言：
: 問題(Question)：
: 這一題為什要從後面看過來算LIS 跟LDS
: 為什從第一個算會錯誤...
: http://ppt.cc/s3cm
: 討論地方 1 2 4 3 7 6
: 從第一個算起 7 6 3 2 1 怎來的....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.144.193
※ 編輯: dqIpb 來自: 59.115.144.193 (08/24 11:38)
討論串 (同標題文章)