NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2003高中組決賽
 NPSC 2003 高中組 決賽 G.考古問題

作者 主題: NPSC 2003 高中組 決賽 G.考古問題  (閱讀 1994 次)

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
NPSC 2003 高中組 決賽 G.考古問題
« 於: 七月 15, 2011, 06:08:46 pm »

題目是這樣的:

給兩個序列,輸出最長的一組遞減的LIS,保證同一個序列每個數字只出現一遍,N<=512


我們可以把他想成一張DAG,每個數字都是一個節點。

然後A->B有邊的條件:(1)A在序列1和序列2都排在B之前 (2)A比B大。

建完之後求DAG最長路,總複雜度O(N^2)


話說這題好像還有其他作法...
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2003高中組決賽
 NPSC 2003 高中組 決賽 G.考古問題