作者bleed1979 (十三)
站內Prob_Solve
標題[問題] SPOJ 1774. All Discs Considered [ALL]
時間Thu Oct 13 23:08:43 2011
感謝兩位相關討論者，快速的做法正如板友所提。
建立adj list，計算最長adj path，
如果最長path分別來自兩個不同DVD，max adj path + 1 + 2
如果僅來自同一片DVD，max adj path + 2
眉角在於下面的圖
DVD1 XXXXXXXX OOOOOOOOOOOOOOOO
XO
DVD2 OOOOOOOO XXXXXXXXXXXXXXXX
X代表一條path，O代表一條path，交叉於XO點。
那麼，不管是先算path X還是path O，
請用一個陣列位置把XO之後的長度記錄起來。
這樣跑到XO點時，就直接加上長度即可。
每次都跑到path最尾巴的話，很容易就TLE。
另外，像XXXXXXXX的每個X都在同一片DVD的話，長度是不用增加的，僅計算換片次數。
這是相關代碼，看不懂說明者就直接看程式碼吧～
http://pastie.org/2693308
======================================================================
http://www.spoj.pl/problems/ALL/
2片DVD，容量分別是N1和N2首歌，所以總共會有N1 + N2首歌。
給定第幾首歌和第幾首歌的前後順序(1 3代表第3首要在第1首之前)，
試問：開始放入某片DVD的1次 + 其中交換片X次 + 最後拿出某片DVD的1次
總共會有幾次動作？
我想到的是topological sort，不過TLE。
無法從單純的數字關係想出什麼快速的解法，請教各位了。
先貼上TLE的code：
http://pastie.org/2689400
現在嘗試DP解, wait...
--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 114.25.246.54
1F：→ tkcn:我猜是建出 DAG 後用 DP 算次數，O(n) 可完成。 10/13 23:12
thx, 我試試看。
※ 編輯: bleed1979 來自: 114.25.246.54 (10/13 23:18)
2F：推 Fenikso:模擬題. 一開始兩片選一片放, 之後的動作全部固定 10/14 02:58
3F：→ Fenikso:各模擬一次取比較小的就是了 10/14 02:59
※ 編輯: bleed1979 來自: 114.25.246.54 (10/14 15:14)