PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[已解決] SPOJ 1774. All Discs Considered [ALL]

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間13年前 (2011/10/13 23:08)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串1/1

感謝兩位相關討論者，快速的做法正如板友所提。建立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