作者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)