NPSC補完計劃
一月 21, 2021, 08:22:58 pm
歡迎光臨,
訪客
請
登入
或
註冊帳號
.
一小時
一天
一週
一個月
永遠
請輸入帳號, 密碼以及預計登入時間
最新消息:
歡迎光臨NPSC補完計劃
首頁
說明
搜尋
登入
註冊
NPSC補完計劃
»
NPSC高中組
»
NPSC2003高中組決賽
NPSC 2003 高中組 決賽 G.考古問題
« 上一篇
下一篇 »
頁: [
1
]
列印
作者
主題: NPSC 2003 高中組 決賽 G.考古問題 (閱讀 2776 次)
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)
話說這題好像還有其他作法...
記錄
列印
頁: [
1
]
« 上一篇
下一篇 »
NPSC補完計劃
»
NPSC高中組
»
NPSC2003高中組決賽
NPSC 2003 高中組 決賽 G.考古問題