我猜正解是DP吧XD。

第一次發現 LIS 的 圖論解法,這題就是要找兩個共有的 LIS(題目是遞減)。

A序列中有 a, b,若 A_idxa<A_idxb && a>b && B_idxa<B_idxb,則 add(a -> b)。

圖建好就找 最長路 求答案,紀錄pre[ ] 復原路徑,使用 SPFA。

我的code

http://snipt.org/Aaigg4

p.s: 感謝 poloo5582 學長。沒有答案就印出一行空白行。

       以 POJ2533 為例 http://ckhs1328.pixnet.net/blog/post/149225996

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()