留言

主題:

2001的題目的一些問題

留言人:

留言日期: 2003/10/22 上午 10:09:11
留言IP:  
留言內容: 請問有人知道2001年國中組題目E 撿石頭 的解法嗎? 因為那題的情況很多ㄟ, 可能前面有1個大的可以撿, 但是如果捨去不撿, 而使後面能夠撿更多的話, 那情況就多了, 還是說主辦單位的輸入資料不會那麼複雜?
目前回應文章
回覆人 主題 回覆日期
火星人刑事Re:2001的題目的一些問題:2003/10/22 下午 08:48:47
火星人刑事Re:2001的題目的一些問題:2003/10/22 下午 10:13:37
Re:2001的題目的一些問題:2003/10/23 上午 08:53:35
該是時候了:2003/10/24 下午 10:19:18
下一頁 最後一頁 頁次:1/1
我要回覆
您所選擇的文章內容

主題:

Re:2001的題目的一些問題

暱稱:

火星人刑事
留言日期:2003/10/22 下午 08:48:47
留言IP: 
內容:>請問有人知道2001年國中組題目E 撿石頭 的解法嗎? 因為那題的情況很多ㄟ, 可能前面有1個大的可以撿, 但是如果捨去不撿, 而使後面能夠撿更多的話, 那情況就多了, 還是說主辦單位的輸入資料不會那麼複雜?

這是一題很經典的題目, 稱為最長遞增子序列,
為Dynamic Programming演算法的基本作業...

只是比較麻煩的是這次的序列長度可以多達10^5個數字,
單純的Θ(n^2)的演算法應該是沒辦法在時間內跑完,
我剛才嘗試光是跑10^10的空迴圈就跑了數十秒,
即使跑得完也是非常time critical,
我認為應該是要改變DP table的存法來爭取執行時間...
不過最近的動畫有不少好看的所以懶得實作了. :p
回到首頁 聯絡我們 留言版 常見詢答 最新消息 我們的服務